[<prev] [next>] [<thread-prev] [day] [month] [year] [list]
Date: Sun, 23 Feb 2014 18:03:05 -0800
From: Jeff Keller <jakeller@...r.com>
To: john-users@...ts.openwall.com
Subject: Re: False positives essay :)
I should add that if anyone else wants to take a whack at cracking this, you can download the hash and a few possible words here:
https://www.dropbox.com/s/roo4jrr8c22uiki/jeff-sparsebundle-hash.zip
I will pay a reward to whomever can free my photos from this damn sparsebundle.
Thanks,
Jeff
On Feb 23, 2014, at 2:55 PM, magnum <john.magnum@...hmail.com> wrote:
> This ended up long and might be of public interest so I cc the list:
>
> On 2014-02-23 22:40, Jeff Keller wrote:
>> Out of curiosity, how does it come up with false positives?
>> Isn’t there only *one* password that would work?
>
> It sure is, but in this case we have a hard time detecting when we got the right one. For login passwords it's simple: The hash is made my feeding the password through a one-way function F, that in it's crudest form is just a single SHA1, for example. So
>
> hash = SHA1("correct password")
>
> When we brute force, we know the hash but not the password. So we just do lots of
>
> hash2 = SHA1("password candidate")
>
> and compare our hash2 with the correct hash. When they match, we have found the correct password. Very simple, no false positives, no false negatives.
>
> Now, for disk or file encryption we don't have a hash! The DMG image was basically made like this when created:
>
> key = F("correct password")
> encrypted_data = AES(key, plain_data)
>
> We obviously do not know the key. We do have an encrypted block (eg. first or last block from filesystem, not a block from any particular file) from the DMG. The encryption is symmetrical so you decrypt using the same key. When we brute force, we do
>
> key = F("password candidate")
> decrypted_block = AES(key, encrypted_block)
>
> The thing is that if we use the wrong key [ie. derived from the wrong password], AES will NOT emit any "error" but a perfectly fine output block of random garbage. Herein lies the problem: How do we know the decrypted_block is correct or not? We don't have any correct data to compare with!
>
> So we are forced to check for "known plaintext" within the decrypted block. All false positives in this case came from a test for the string "Apple" within the decrypted block. While the chance for that string appearing in a specific spot in random data would be about one in a thousand billions, the chance for it appearing *anywhere* within a block of 8 KB is much greater. I'm not sure but I think it's in the order of one in 134 millions. We got 5-6 false positives in
> ~20 hours at ~5000 c/s which might indicate it's slightly more probable so I'm not sure about the exact figures.
>
> All other known-plain tests in the format are at least 8 bytes and that wont give any false positive in 20,000 years or so. The problem is we are not 100% sure we can do without the "Apple" test. We think we can, but we are not sure. If we drop that test and your decrypted block really has the "Apple" string but none of the other strings we test for, we'd end up with a false NEGATIVE instead, which as you can imagine is much, much worse. Shrug.
>
> magnum
>
>
---
Jeff Keller
Senior Writer, Digital Photography Review
www.dpreview.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.
