Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Fri, 12 Aug 2011 17:26:36 -0700
From: Corbin Simpson <mostawesomedude@...il.com>
To: john-users@...ts.openwall.com
Subject: Re: Tripcodes, take 2

Hi,

Now that Defcon's over (congrats on doing so well! I should
participate next year!), I figured I'd follow up on this a bit.

The traditional example uses a not-politically-correct word, so I'm
going to use the example username "corbin" and password "simpson".

As a trip, the plaintext looks like "corbin#simpson" and encrypts to
"corbin!Rk7VUsDT2U".

The algorithm's dead-simple for ASCII input, and I'll assume that for
now. (Unicode/JIS/Latin-1 input needs to go through a lookup table
first.) The salt is the second and third characters of the trip; if
the trip's too short, the padding "H.." is used. A short lookup table
is used to map each character of the salt into ASCII alphanumerics.
Then crypt() (DES with salt) is used, and the tail of the ciphertext
(no salt!) is the result.

A quick example: "simpson" has the second and third characters "im",
which are alphanumeric, so no substitutions are needed. Then
crypt("simpson", "im") is called, resulting in "imjRk7VUsDT2U". The
salt is clipped off, leaving "Rk7VUsDT2U", and that's presented with
the original username.

Some weird things about the format: The username doesn't matter, the
salt isn't stashed with the ciphertext but depends on the plaintext,
and the input lines are a bit weird, with the bangs and sharps instead
of normal colons.

So, my initial thought was to just run all possible salts (63**2 =
3969) on each attempted plaintext. But that's wasteful. My next
thought was to grab the salt from the inputted plaintext, and use
that, for each round. But then I got very confused, and after reading
some papers, I think I missed something fundamental: John runs
multiple DES rounds in parallel, doesn't it? Single key, multiple
plaintexts? If that's the case, then the salt is set once and then
never touched.

I'm now thinking about alternative approaches. I could write down the
salts for each of the inputted plaintexts, setting each salt and
running each plaintext, but that seems really really excessive, since
there will be repeat inputs. For example, if "gam", "gin", "yam", and
"yin" are all in the dictionary, then it's possible that the salts
"am" and "in" will be applied for those inputs multiple times, which
wouldn't work out.

I can't find any papers on it; how exactly does DES salting work? Does
it alter anything besides key schedule? Is it expensive enough to
warrant a specialized plaintext traversal instead of swapping the salt
for each key? I know that exploratory tripcode crackers tend to stick
on a single salt for as long as possible, but that might not be the
best approach for trying to crack a tripcode.

On the plus side, I think I know enough about John's guts that I could
probably go reuse John's DES routines in a more general, crypt()-based
tripcode cracker, but I really want to see if I can't get this
shoehorned in somehow.

Maybe this is a guess out in left field, but is it possible to
sidestep the format subsystem?

~ C.

On Thu, Aug 4, 2011 at 12:41 AM, Frank Dittrich
<frank_dittrich@...mail.com> wrote:
> Am 03.08.2011 23:30, schrieb Solar Designer:
>> However, to get a more reliable answer you need to provide an example.
>> I am not familiar with tripcodes, and few in here are. So please post
>> an example input to JtR (with your future patch) and the desired output,
>> and show how to verify that this is the correct output.
>
> Not having much time either, here's a wikipedia link:
>
> https://secure.wikimedia.org/wikipedia/en/wiki/Tripcode
>
> The article contains a description of the algorithm.
>
> The German article
> https://secure.wikimedia.org/wikipedia/de/wiki/Tripcode contains a
> sample implementation in perl (Chapter "Beispielimplementation"), but it
> seems to be missing the first step ("Convert the input to Shift JIS.").
>
> Frank
> **
>



-- 
When the facts change, I change my mind. What do you do, sir? ~ Keynes

Corbin Simpson
<MostAwesomeDude@...il.com>

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.