Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Thu, 4 Jul 2013 19:39:43 +0200
From: Truls Edvard Stokke <trulses@...il.com>
To: john-users@...ts.openwall.com
Subject: Re: Using JtR to generate tripcodes

On Thu, Jul 4, 2013 at 8:40 AM, Solar Designer <solar@...nwall.com> wrote:

> On Wed, Jul 03, 2013 at 10:30:58PM +0200, Truls Edvard Stokke wrote:
> > Users of text/imageboards frequently search for novelty tripcodes (i.e.
> > tripcodes with certain phrases in them), usually this is done by
> generating
> > a very large number of them and then running the output versus a regex or
> > something to that effect (which is why I can't just keep them in the
> binary
> > format).
> >
> > To that goal I would like to use JtR (or at least some part of it) to
> > generate a lot of them.
>
> JtR can crack DES-based tripcodes fine, but searching for novelty
> tripcodes is a somewhat different task, which JtR is not well-suited
> for.  What do you not like about the existing tools that readily do what
> you need?  What extra do you hope to achieve by using JtR?  What
> performance do they achieve at this?
>

All the existing tools I have seen are stuck with SSE2, JtR provides (at a
glance) very efficient and up to date bitslicing DES implementations that
keep up with new instruction sets, and the internal API seems quite stable
(I'm aware that no promises have been made in this regard ;-). From a
portability standpoint JtR is also very appealing, providing DES
implementations for several architectures.

Some of the existing tools are Windows based GUI programs with either no
source code or source code in all Japanese. The Japanese trip generators
are usually the highest quality but are made to work with 2chan's trip
format, which is incompatible with the western 4chan's trip format for
certain inputs (has something to do with the encoding, unrelated to the
actual DES part, suffice to say different bits make it to the IP).

Lastly, very few programs get the more "eccentric" features of tripcodes
right, the actual "keyspace" that you're able to input to for instance
4chan is a lot smaller than the entire DES keyspace (I apologize if this
terminology is incorrect, I'm a layman after all) every tripcode has to
abide by very specific rules with relation to the translation of the input
from UTF-8 to SJIS, so the tripcode generators that attempt to brute force
the entire DES keyspace will frequently generate tripcodes that you are
unable to input to 4chan or will yield a different result than expected due
to change in encoding. There's also certain characters that expand into
their corresponding HTML entities, the '&' character for instance expands
into "&quot;" and suddenly an 8 character tripcode is effectively a 3
character tripcode (maybe this is of interest to people who attempt to
crack them). I have made a program that implement all of these rules
correctly, unfortunately it's very slow as it is based on OpenSSL's
DES_fcrypt, my goal is to create a JtR based program that only checks
relevant parts of the keyspace.


>
> > From what I can tell it's possible to modify the DES_bs_get_hash function
> > (DES_bs.c:331 john-1.8.0) to extract all the 64 bits required to get a
> > result on the same form as what DES_bs_get_binary (DES_bs.c:281
> john-1.8.0)
> > returns from a cipher text, and I assume all the information from the
> > cipher text is retained in the binary format, but I don't know how to go
> > from the binary format to the cipher text.
>
> You could implement that, yes.  You would need to extract the 58 bits
> that tripcodes actually use, perform DES final permutation, and finally
> perform the crypt(3)-style base 64 encoding and the regexp check (or
> whatever).  However, that would reduce performance a lot.  Normally,
> bitslice DES produces many ciphertexts at once, and they're compared
> against those loaded for cracking with an efficient algorithm that does
> not require processing each of the computed ciphertexts individually.
> As you can see, what you're trying to do is just that - processing of
> each of the computed ciphertexts individually - and it'd slow things
> down a lot.
>
> Alternatively, you could keep some of these final steps reversed, but
> then you can't do e.g. a direct regexp check - you need to implement a
> pre-check for would-be-good-looking tripcodes working from their
> intermediary form (such as prior to DES final permutation) and in a
> vectorized manner (so that you would not have to process each of them
> individually).  It's a challenging task, and I'm not available to help
> you with it (sorry!)
>
>
Thanks for the good advice, I realize that getting something actually
efficient will not be very straightforward, hopefully I will be able to
operate directly on DES_bs_all.B (from what I understand this is the matrix
that holds the resulting ciphers in the binary format) at some point in the
future, but first things first.

Once upon a time I made a very bad MPI tripcode bruteforcer based on an old
(pre tripcode support) version of JtR, my understanding of the format at
the time was very lacking so the actual program is deeply flawed. But I
learned enough about the JtR API to understand that I have to cache keys
based on salt and attempt to only run DES_BS_DEPTH keys at the time and all
that.


> To summarize: if you wanted to do this due to JtR's performance at
> tripcodes, you won't achieve that with the straightforward approach, and
> the better approach is complicated.  So you're probably out of luck.
>
> > I am wholly unfamiliar with DES, where do I go from here?
>
> The only thing you'd need to know about DES is its final permutation.
>
>
I did the FP and I was able to create the inversion of DES_raw_get_binary
(DES_std.c:1112 john-1.8.0) except for the last character, two of the bits
from the last character are discarded into block[2], I assume they are not
important however as tripcodes seem to end only with 16 different
characters, thanks for pointing me to crypt(3) for the final encoding I'll
have a look at it and probably work it out from there.


> You also need to understand the concept of bitslicing - see Eli Biham's
> paper for that.
>
> Good luck!  (And I'm afraid that you're on your own with this...)
>
>
Thank you so much for your time.


> Alexander
>

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.