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.
2AB, 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 2AB)


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 bruteforce  but I don't know whether a better than bruteforce scenario would be possible here. Try searching the web for SHA256 and knownplaintext 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 AB 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(AB). 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 nonclassified 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(AB)  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 AB 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 partialmessage collision. If any portion of the message in your case AB 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 partialmessage collision or nearmessage collision.
Fire Ant


Back to top 


