View previous topic :: View next topic |
Author |
Message |
Paul42 Just Arrived
Joined: 20 May 2010 Posts: 0
|
Posted: 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
|
|
Back to top |
|
|
p____h Just Arrived
Joined: 13 May 2010 Posts: 0 Location: Poland
|
Posted: 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)
|
|
Back to top |
|
|
capi SF Senior Mod
Joined: 21 Sep 2003 Posts: 16777097 Location: Portugal
|
Posted: 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.
|
|
Back to top |
|
|
Paul42 Just Arrived
Joined: 20 May 2010 Posts: 0
|
Posted: 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
|
|
Back to top |
|
|
p____h Just Arrived
Joined: 13 May 2010 Posts: 0 Location: Poland
|
Posted: 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
|
|
Back to top |
|
|
capi SF Senior Mod
Joined: 21 Sep 2003 Posts: 16777097 Location: Portugal
|
Posted: 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.
|
|
Back to top |
|
|
Fire Ant Trusted SF Member
Joined: 27 Jun 2008 Posts: 3 Location: London
|
Posted: 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
|
|
Back to top |
|
|
|