DES again.

Martyr

i asked before if anyone knew any DES cracking shortcuts/speedups
long time ago.

anyway, bitslice as i found turned out to be very fast on 64-bit cpus,
and there was excellent source in the distributed.net clients, aswell as
in a program by svend olaf mikkelson called bryd400 'bryd' meaning 'crack' in danish.

was gonna write an nt password cracker at time with GUI similar to something
like LC or Saminside, except have it open source...(not a virus, as some suggested. what i said in post was theory,not plan)

was thinking about whether to bother now with free version as,
i think most people can get hands on free copy of lc/saminside anyway
no source, but i don't think they would be too bothered.

and looking at some progress i made on trying to speed up DES at that time, it just wasn't good enough compared to either product.

don't understand the mathematics behind DES, which is why i didn't consider
this anything worth pointing out, but! you might be interested.

i know des can have up to 70 quadrillion possible keys, but how many
people that used des in the past, would actually use a key
made up of non-alphabetical characters???

can probably guess that, majority of keys were no more than a combination of some letters/numbers.

getting to the little speed up, it works best on SSE processors with
128-bit wide registers.
basically, you bit-or each key schedule against others to generate new ones.
of course, at the time i was thinking about it, the purpose was to crack LM
hashes, which are product of DES, so only uppercase characters are used.

simple example for using A-Z character set.

Create 3 key schedules for the strings "A", "B" and "D"

Below shows that bit-OR'ing the key schedules of "A" with "B" will
produce the key schedule of "C" .

And the rest work in the same way.

(A | = C
(A | D) = E

(B | D) = F
(E | C) = G

and from those, you can generate the rest.
numbers can be done similarly

create 0,1,2,4 and 8
to produce 3,5,6,7 and 9

(1 | 2) = 3

(1 | 4) = 5
(2 | 4) = 6
(3 | 4) = 7

(1 | 8) = 9

if you can write a routine, that bit-ors the key schedules
against each other, you don't have to call the key setup routine..except
maybe first time(5 calls instead of 26) or pre-compute.
just encrypt the plaintext, and test if its same as ciphertext.

another thing, which is more obvious, is to pre-compute
the plaintext using (IP)initial permutation, and "reverse" the des
hash using IP routine also.

maybe there is similar technique used in lc/saminside??

bitslicing the lm hash is still by far the fastest method, but not suitable
to a large table of ciphertext (passwords)
and the table method is fine too, but still takes considerable time to generate.

so, i'm asking again, if anyone knows of any shortcuts, any at all, please share them.:)

other algorithms too would be nice to know about!

crashedmind

Hi Average Joe,

I'd suggest checking out the research papers on http://citeseer.ist.psu.edu to see what people are doing.

A lot of current approaches are based on knowing either some or all of the plaintext and/or ciphertext or based on fault or power analysis.
My understanding is that your approach is more based on bruteforcing based on algorithmic speedups - is that correct?

An interesting approach to bruteforce cracking is Rainbow tables - can be used quite effectively against lm hashes.

Regarding precomputation of key schedule - there might be some benefit to precomputing the key schedule for N keys in advance/offline. I guess it's a tradeoff between time/memory.

Is there any merit (if possible) in operating directly on the subkeys i.e. manipulate the subkeys directly to avoid the key schedule process. Or is this what you mean by XORing the key schedules. This approach assumes that once you find the correct subkeys you can work backwards to determine what the key associated with those subkeys is.
The IP and FP stage can be skipped in a similar manner also I think.
This is all off the top of my head - it's been a while since I played with des internals.

Regarding des key entropy, most half-decent software that generates a key based on user input will perform some one-way function on the user input first e.g. sha1 hash to produce a more random key, or salt it, rather than take the user input directly.

crashedmind

Gavin

If you are looking at brute forcing, as mentioned, and want to simply get the fastest implementation of DES possible, maybe investigate using the newer hugely parallel graphics cards for an implementation.

You've most likely come across it already if you are in any way interested in crypto, but the Handbook of Applied Cypto is very good. http://www.cacr.math.uwaterloo.ca/hac/about/chap7.pdf

Chap7 deals with block ciphers.

Are you in college ? There are a few very good crypto guys in Ireland, Mike Scott in DCU is a good person to talk to if you have an interesting project. Particularly in crypto implementation, which is his forte.

Gav

Martyr

sorry for late response.

My understanding is that your approach is more based on bruteforcing based on algorithmic speedups - is that correct?

yes.

i don't have a need for an nt password cracker.i just spent some time trying to find ways of speeding DES up last year for the purpose of writing something similar to elcomsoft/insidepro/atstake password crackers, except making an open source version.

i gave up on idea of writing program, because of limited knowledge on gui development for windows, and lack of programming tools at time.

An interesting approach to bruteforce cracking is Rainbow tables - can be used quite effectively against lm hashes.

this is good for LM, agreed, a ciphertext/hash with no challenge/salt, but not otherwise as i'm sure you know, which is where trusted brute force or some other method is used.

Regarding precomputation of key schedule - there might be some benefit to precomputing the key schedule for N keys in advance/offline. I guess it's a tradeoff between time/memory.

the plan was, given 'ABCD' as character set string, create a key schedule for each character at 7 different indexes.
like 'A'

ks1 - 0x41,0x00,0x00,0x00,0x00,0x00,0x00
ks2 - 0x00,0x41,0x00,0x00,0x00,0x00,0x00
ks3 - 0x00,0x00,0x41,0x00,0x00,0x00,0x00
ks4 - ...
ks7 - 0x00,0x00,0x00,0x00,0x00,0x00,0x41

imagine if you will, above are key schedules, and rest of characters are processed too.

bit-OR ks1 of 'A' with ks2 of 'D' and then we have key schedule of 'AD'
without calling set key routine.

using SSE2 128-bit registers, its pretty fast to just OR the values of each key schedule against each other, rather than call seperate routines each time a new key is tried.(its kinda lame tbh, but it was fastest i could get it)

you can "reverse" the ciphertext with IP, aswell as pre-compute the IP on plaintext.

do 15 rounds, check 1 part of the output, if its not equal to first part of ciphertext, do next key.
else do 16th and compare with second part of ciphertext, if equal, found password.

poor algorithm, but you get the idea. :rolleyes:

Is there any merit (if possible) in operating directly on the subkeys i.e. manipulate the subkeys directly to avoid the key schedule process. Or is this what you mean by XORing the key schedules.

these programs do that.

bryd400:http://home19.inet.tele.dk/svolaf/index.htm
bdes:http://home19.inet.tele.dk/svolaf/des.htm

but don't accept custom character sets from the user.

If you are looking at brute forcing, as mentioned, and want to simply get the fastest implementation of DES possible, maybe investigate using the newer hugely parallel graphics cards for an implementation.

i read up on that after a friend suggested the idea.
it seems the gpu is not suitable for stream/symmetric block cipher implementation with current apis, due to byte-level operations required.

you can read more here if interested.
http://www1.cs.columbia.edu/~dcook/pubs/CTRSA-corrected.pdf

Are you in college ? There are a few very good crypto guys in Ireland, Mike Scott in DCU is a good person to talk to if you have an interesting project. Particularly in crypto implementation, which is his forte.

yes, i'm in college, no project.

honestly, i don't really know much about crypto, just the basics.
i've implemented a few hash/block/stream ciphers in 32/64-bit asm, thats about it.

i think if i were talking to those people about cryptography, they'd probably figure out soon enough i am a bit of a fool on the subject

crashedmind

Hi AverageJoe,
OK I understand what you're saying.

Taking a step back...

What kind of performance improvement do you expect from the keyshedule optimisation? I'd guess we're talking about approx a 2^1 time improvement at best.

The other approaches mentioned in original post for known plaintext attack (linear and differential cryptanalysis) yield a much more significant time improvement. approx. equivalent to approx 2^40 des operations. That's obviously a 2^16 improvment on standard bruteforce attack.
There's a good / understandable paper on these approaches here: http://www.engr.mun.ca/~howard/Research/Papers/ldc_tutorial.html

One interesting / exploitable feature / shortcut specific to DES is the Complimentation property where if you bit invert the plaintext and the key the resulting ciphertext is the inverse (of what it would have been for a non-inverted plaintext and non-inverted key). That's approx a 2^1 time improvement for chosen plaintext brute force attack.

You mentioned that the general application is a password cracker along the lines of that from elcomsoft. If you know the document type that's encrypted, then you can exploit the fact that the document most likely starts with a fixed header so you know some of the plaintext e.g. for jpg the first 4 bytes are FF D8 FF E0.

crashedmind

Martyr

crashedmind wrote:

What kind of performance improvement do you expect from the keyshedule optimisation? I'd guess we're talking about approx a 2^1 time improvement at best.

Svend Olaf Mikkelson already done a key schedule routine in assembly some years ago which is 2 times faster than the routine in OpenSSL.

The way i was describing, some tests showed it to be about 3-4 times faster, because the key setup routine wasn't called, except for initialising key schedules of each character supplied by user with a custom set.

The other approaches mentioned in original post for known plaintext attack (linear and differential cryptanalysis) yield a much more significant time improvement. approx. equivalent to approx 2^40 des operations. That's obviously a 2^16 improvment on standard bruteforce attack.

Would these attacks work against LM passwords?

NT Lanman hashes are the plaintext "KGS!@#$%" DES-ECB mode encrypted with the 56-bit DES key of the users password.

AFAIK, linear and differential methods require pairs of ciphertext, no?
i'll read that article so.

crashedmind wrote:

One interesting / exploitable feature / shortcut specific to DES is the Complimentation property where if you bit invert the plaintext and the key the resulting ciphertext is the inverse (of what it would have been for a non-inverted plaintext and non-inverted key). That's approx a 2^1 time improvement for chosen plaintext brute force attack.

is this what you mean??

i tried this, plaintext is.."PLAINTEXT", and the key is "KEY"

1st Ciphertext:0x8195CF651264E4B8

If the bits of "PLAINTEXT" and "KEY" are inverted.

2nd Ciphertext:0x7E6A309AED9B1B47

inverting the 1st ciphertext, will give 0x7E6A309AED9B1B47 also.

it says in Applied Crypto page 281 about Complement Keys:

'This isn't anything mysterious. The subkeys are XORed with the right half after the expansion permutation in every round. This complementation property is a direct result of that fact.'

You mentioned that the general application is a password cracker along the lines of that from elcomsoft. If you know the document type that's encrypted, then you can exploit the fact that the document most likely starts with a fixed header so you know some of the plaintext e.g. for jpg the first 4 bytes are FF D8 FF E0.

well, i was thinking more along the lines of cracking nt passwords, just LM/NTLM1 with brute force/dictionary attack rather than a DES cracker.

crashedmind

The overall point I'd make is the best way to optimise your efforts is to exploit the vulnerabilties of the system under analysis rather than optimising des performance.
Of course, you can combine the two approaches which I'll assume is what you intended.

Average Joe wrote:

Svend Olaf Mikkelson already done a key schedule routine in assembly some years ago which is 2 times faster than the routine in OpenSSL.

The way i was describing, some tests showed it to be about 3-4 times faster, because the key setup routine wasn't called, except for initialising key schedules of each character supplied by user with a custom set.

That's pretty good. I'm familiar with openssl implementation of des and it's pretty fast as compared to lots of other implementations out there.

Average Joe wrote:

Would these attacks work against LM passwords?

NT Lanman hashes are the plaintext "KGS!@#$%" DES-ECB mode encrypted with the 56-bit DES key of the users password.

AFAIK, linear and differential methods require pairs of ciphertext, no?
i'll read that article so.

No - they would not be suitable for NT Lanman hashes.
NT Lanman hashes have several significant exploitable vulnerabilties that make the cryptanalysis a lot easier than a dumb des bruteforce:
1. Changing password to upper case
2. appending known plaintext of all zeros for passwords less than 14 chars.
3. It is easy to determine if a password is less than 7 chars in length.
etc...

Average Joe wrote:

is this what you mean??

i tried this, plaintext is.."PLAINTEXT", and the key is "KEY"

1st Ciphertext:0x8195CF651264E4B8

If the bits of "PLAINTEXT" and "KEY" are inverted.

2nd Ciphertext:0x7E6A309AED9B1B47

inverting the 1st ciphertext, will give 0x7E6A309AED9B1B47 also.

it says in Applied Crypto page 281 about Complement Keys:

'This isn't anything mysterious. The subkeys are XORed with the right half after the expansion permutation in every round. This complementation property is a direct result of that fact.'

Yes. Agreed there's nothing mysterious about it - but it can used as an exploitable vulnerabilty against DES. AES does not have this property.

Average Joe wrote:

well, i was thinking more along the lines of cracking nt passwords, just LM/NTLM1 with brute force/dictionary attack rather than a DES cracker.

Martyr

crashedmind wrote:

The overall point I'd make is the best way to optimise your efforts is to exploit the vulnerabilties of the system under analysis rather than optimising des performance.
Of course, you can combine the two approaches which I'll assume is what you intended.

i know for sure, i need to do something other than brute force, but i don't know any type of analysis.
all i've seen against NT Lanman passwords, is brute force.

crashedmind wrote:

NT Lanman hashes have several significant exploitable vulnerabilties that make the cryptanalysis a lot easier than a dumb des bruteforce:

What cryptanalysis?
I'm open to ideas, i'd be willing to try any method if it works.

crashedmind wrote:

1. Changing password to upper case
2. appending known plaintext of all zeros for passwords less than 14 chars.
3. It is easy to determine if a password is less than 7 chars in length.
etc...

All LM passwords are converted to uppercase.understood.
The full LM hash is made up of 2 DES blocks of ciphertext,
so if the first password is 7 characters or less, then the ciphertext for second part will always be: 0xAAD3B435B51404EE.

C:\des_test>des_test KGS!@#$% PASS

Hex 64-bit key:0x5120546B31010101 Plaintext:0x4B47532140232425

Ciphertext:0xB267DF22CB945E3E

C:\des_test>des_test KGS!@#$% ""

Hex 64-bit key:0x0101010101010101 Plaintext:0x4B47532140232425

Ciphertext:0xAAD3B435B51404EE

the 2 DES blocks concatenated make up LM hash:0xB267DF22CB945E3EAAD3B435B51404EE

crashedmind wrote:

Yes. Agreed there's nothing mysterious about it - but it can used as an exploitable vulnerabilty against DES. AES does not have this property.

How?
I just thought if there was a vulnerability, then it would have been mentioned in the book.

i'm not questioning your knowledge of DES, but i don't see how this complement property makes it 2 times faster to crack.

after a search, i found this short text.

P3.10 (b)
Due to the (S)DES complement property, we can get two encryptions for the price of one, since after computing Y = K{X} we know that Y' = K'{X'}. But this does not seem to reduce the work needed for a brute-force attack on a particular key K, since K' is a different key.

probably a bad example, but as i understand it..because the plaintext has to be inverted aswell as the key..you're not really gaining anything in speed.

correct me if i'm wrong.

crashedmind

Average Joe wrote:

i know for sure, i need to do something other than brute force, but i don't know any type of analysis.
all i've seen against NT Lanman passwords, is brute force.


What cryptanalysis?
I'm open to ideas, i'd be willing to try any method if it works.

Given that the system in this case (lm hashes) is used to encrypt user passwords then I'd say the best method of attack is to exploit the general characteristics of passwords.
This approach would be a "smart" brute force where, by making some educated guesses, we reduce the work effort over a "dumb" brute force where all permutations are tried.
There are good descriptions of most common password characteristics for English and other languages and even pre-built dictionaries.
So first approach might be a dictionary attack based on common password characteristics.
This dictionary could include names, places, words, and numeric substitutions for letters etc...
You can build this dictionary and generate associated hashes offline. Storage will limit the size of your dictionary but then you can do clever things to offset this.
Rainbow tables were already mentioned.
See http://www.beginningtoseethelight.org/ntsecurity/#293D8AA3290CF42C for a good technical analysis of building tables of values with associated lm hashes offline.

Average Joe wrote:

How?
I just thought if there was a vulnerability, then it would have been mentioned in the book.

i'm not questioning your knowledge of DES, but i don't see how this complement property makes it 2 times faster to crack.

after a search, i found this short text.



probably a bad example, but as i understand it..because the plaintext has to be inverted aswell as the key..you're not really gaining anything in speed.

correct me if i'm wrong.

Question away - I wouldn't claim to be an expert on des or crypto - just know enough to get by

crashedmind wrote:

One interesting / exploitable feature / shortcut specific to DES is the Complimentation property where if you bit invert the plaintext and the key the resulting ciphertext is the inverse (of what it would have been for a non-inverted plaintext and non-inverted key). That's approx a 2^1 time improvement for chosen plaintext brute force attack.

The des complementation property was mentioned in response to the original post looking for des shortcuts. "Vulnerability" depends on the context and the context given was a chosen plaintext attack: where the attacker can choose arbitrary plaintext to be encrypted by the system (under the unknown key) and get the output ciphertext.
For a chosen plaintext attack, this means that half the keys can be tested by computing complements instead of performing a des encryption i.e. keyspace is effectively halved.

Martyr

here is some code that shows the bit-or idea i was talking about.

i just recently updated it with XMM/MMX & unrolled loops.
on an AMD64 3000+ 2.0 Ghz the keys per second is roughly 8.4 million, but on a P4 2.4 Ghz its only 4.2 million

http://www.thesmith.ca/weiss/dcrack.rar

NutJob

Average Joe wrote:

here is some code that shows the bit-or idea i was talking about.

i just recently updated it with XMM/MMX & unrolled loops.
on an AMD64 3000+ 2.0 Ghz the keys per second is roughly 8.4 million, but on a P4 2.4 Ghz its only 4.2 million

http://www.thesmith.ca/weiss/dcrack.rar

Is the P4 hyperthreaded ?????


if so turn it off in thy bios.

Martyr

The AMD64 3000+ supports HT so i don't know if that is the reason, the pc i tested on was not mine & i wouldn't be able to change BIOS settings.

one guy said that the AMD64 3000+ was more like a P4 3.5 Ghz in terms of speed..

what i noticed was old Pentium optimised code runs best on AMD CPU's but slower on P4's, P4 optimised code will still run fast on AMD64 though, not sure about earlier models..

dcrack uses Pentium optimised routines, maybe this is why it runs slower on P4.

a benchmark test carried out with John The Ripper, it was roughly 6 million hashes per second.
L0phtcrack 5 was around 6.5 million & saminside was 8.4 million, dcrack is an average of 8.1 overall.

solar designer told me that John will crack at 12 million per second but when i asked him about it "using a custom character set", he didn't give me an answer & instead felt offended. :P

Because his answer would have been "no" had been honest with himself.

when dcrack is trying multiple hashes, it is much slower than saminside & L0phtcrack & JtR, but the frist 2 programs use some method of precomputation, not rainbow tables, but some trick which isn't documented.