Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Tue, 30 Mar 2010 01:26:38 +0400
From: Solar Designer <solar@...nwall.com>
To: john-users@...ts.openwall.com
Subject: Re: Cracking DES with Probable Plaintext attack?

This is somewhat off-topic, yet I'll provide a reply on the list for now.

On Sun, Mar 28, 2010 at 07:05:08AM -0700, John Doe wrote:
> i have a DES encrypted file and can assume that the plaintext contains ASCII letters with some spaces, .!?-chars and so on.
> Is it possible to crack it with john?

No, not directly or not without code changes.

JtR does not crack encrypted files.  It audits/cracks password hashes.

However, you may use JtR to produce a stream of candidate passwords for
another tool (likely a custom one) to test against your encrypted file.

Alternatively, you may implement support for your file encryption into
JtR.  Although JtR was meant to work on password hashes, there's nothing
to prevent you from having a modified version of it crack an encrypted
file instead.

Here are a couple of older postings that touched this topic:

http://www.openwall.com/lists/john-users/2009/07/10/4
http://www.openwall.com/lists/john-users/2009/01/21/4

> I 've looked into the code, bit-slice DES, sboxes and so on --> is my assumption true that this works only for known-plaintext attacks? (I have the ciphertext and plaintext, and want the key? -

No, you can also have a program try decrypting a piece of your file with
different candidate passwords and then search the decrypted piece for
patterns (e.g., no non-printable characters in a few hundred bytes of
data will very likely indicate correct decryption).

> btw - when is this attack useful? I usually don't have the plaintext, right?)

Quite often, you do have some known plaintext - e.g., the header of a
file that you've encrypted may be full of constants that are dependent
on the file type only.  8 bytes of known plaintext at a known file
offset will be enough for checking for a direct match (simpler than what
I've described above).

> Last question: Is it possible to crack DES with no huge cost effort in reasonable time (2 weeks)?

No, it still costs a lot, unless you have some info that will let you
narrow the key search.  Where did the key come from?  In fact, how do
you know the file is DES encrypted?  What mode of operation?

http://en.wikipedia.org/wiki/Block_cipher_modes_of_operation

> I 've calculated, and came to the result that the machine would have to brute-force 59571 million keys/s

That's correct, although you should expect to hit the correct key in
half the time or with half that keys rate.

> (my current threaded cracker checks 4 million keys/s on a Pentium Dual-Core 2,6Ghz/core).

You should be able to make it 10x faster.  For comparison, on modern
CPUs, JtR achieves over 2M c/s at DES-based crypt(3) per core.  This is
for 25 iterations of DES, so it means over 50 million DES block
encryptions per second per core.  When you're cracking just one DES
encryption and when you intend to search the DES keyspace exhaustively,
some additional optimizations are possible, so 100 million DES keys per
second per core may be realistic for optimal code.  Then you may look
into implementing this on a GPU for even better speed.

> Looks like it won't be possible with high-CPU Amazon EC2 either.

EC2 is somewhat slow, over-priced, and limited to not-too-many instances
by default (from what I've read).

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.