SHA256 security

Networking/Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security

Author: Paul42 PostPosted: Thu May 20, 2010 8:31 pm    Post subject: SHA256 security
    ----
Hello there,

I've been trying to find the answer to this problem but without any success.

I have two numbers A, B.
!A is random!
I publish A and SHA256(AB)
If multiple couples A & SHA256(AB) are known is it possible to mathematically or easily compute B?

Kind regards,
Paulo

Author: p____hLocation: Poland PostPosted: Sat May 22, 2010 2:24 am    Post subject:
    ----
You mean AB=A*B, don't you?

In my opinion it's impossible. SHA256 is a hash function.

The number could be odd or even. If it is an odd, we could divide it by 2.
2|AB, so A could be 2.
We know A=2 and SHA(A*B) and we still can't crack SHA256(), can we?
If we cracked this example, we would crack almost half of cases (every 2|AB)

Author: capiLocation: Portugal PostPosted: Sat May 22, 2010 5:35 am    Post subject:
    ----
I think he means AB as in the concatenation of A and B. As in, if A="123" and B="456" then AB="123456".

At the very least you're diminishing the space you need to brute-force -- but I don't know whether a better than brute-force scenario would be possible here. Try searching the web for SHA256 and known-plaintext attacks.

Author: Paul42 PostPosted: Sat May 22, 2010 10:44 am    Post subject:
    ----
Hello -

Indeed, it means the concatenation...
I haven't found anything about such kind of attacks...

I'll keep on searching

Cheers,
Paul

Author: p____hLocation: Poland PostPosted: Mon May 31, 2010 5:32 pm    Post subject:
    ----
Concatenation ... - IMO the same result. It will give you nothing.

1. A+B means concatenation, where A is only one char. You can guess that char. I mean $hash=sha($text). You can always guess the first char of $text and you still cannot crack $hash.

2. http://en.wikipedia.org/wiki/Salt_(cryptography)
$salt+$text is concatenation. We use salt to be more secure.

IMO if you know A and SHA(AB) there is no way to find B

Author: capiLocation: Portugal PostPosted: Mon May 31, 2010 9:23 pm    Post subject:
    ----
We need to settle on some standard notation here, or things are going to get complicated... I propose we use A|B to mean the textual concatenation of A and B, as is widely used in the description of cryptographic processes (cf. for example RFC 3394, the description of the AES key wrap algorithm).

Now, the premise here wouldn't be so much about deriving B immediately from A, or from SHA(A|B). If that were possible, SHA would obviously be completely broken.

Obviously, if you have hash("abcdefgh") and you know that the message starts with "abcd", you have reduced the universe of possible plaintexts in half -- you now only have to brute force the remaining 4 characters, instead of the original 8. This does not mean that SHA is broken in any way; it's just a matter of brute force with previous knowledge.

What I don't know, though, is whether or not knowing a portion of the original plaintext makes the job of guessing the entire plaintext easier than it would be with normal brute force. That is, in the example above, if knowing the first 4 characters means you can guess the rest in less than the 26**4 calculations it would take to brute force it.

For what it's worth, I highly doubt that you can do this -- or, to be more precise, that any method for doing this has been found so far, and made public. If such a weakness had indeed been found (by non-classified cryptanalysis) then SHA would be considered broken and we would have heard of it by now.

After all, like p____h said, a standard measure in preventing against dictionary attacks involves precisely concatenating a known prefix with the rest of the message before hashing it (this is known as salting). There are several protocols which transmit A (the salt) in cleartext, along with hash(A|B) -- including for example SSL, which is used in HTTPS.

Author: Fire AntLocation: London PostPosted: Sun Jun 12, 2011 10:49 am    Post subject:
    ----
Hi Paulo,

There are two points I can make here:

First is that hashing A|B and publishing A is NOT a good idea. You are drastically reducing the brute force

The second point, since you didn't specifically mention which version of SHA I will assume SHA 0 & 1which IS susceptible to a partial-message collision. If any portion of the message in your case A|B is known then it is possible to derive the other portion better than using brute force.

If you want to learn more then just Google partial-message collision or near-message collision.

Fire Ant



Networking/Security Forums -> Cryptographic Theory and Cryptanalysis - Internal and Transmission Security


output generated using printer-friendly topic mod, All times are GMT + 2 Hours

Page 1 of 1

Powered by phpBB 2.0.x © 2001 phpBB Group