 |
|
| Science Forum Index » Cryptography Forum » Can birthday problem be applied in bruteforce... |
|
Page 1 of 1 |
|
| Author |
Message |
| Bipin... |
 Posted: Tue Sep 29, 2009 9:47 am |
|
|
|
Guest
|
Hi,please consider my novice question:
i was reading the Birthday problem in wikipedia
http://en.wikipedia.org/wiki/Birthday_problem
"In a group of at least 23 randomly chosen people, there is more than
50% probability that some pair of them will have the same birthday.
Such a result (for just 23 people, considering that there are 365
possible birthdays) is counter-intuitive to many. For 57 or more
people, the probability is more than 99%"
Question: So, to bruteforce a randomly choose 128 bit key, only 3.1 ×
10^19 random tries are necessary to find the key? (considering
birthday problem/attack)? [1] So, can birthday problem be used
effectively to find for a randomly choosen key, with random bruteforce
attack? Could this way be quicker than a full keyspace search with
bruteforce?
Ref chart(Desired probability of random collision (p)):
http://en.wikipedia.org/wiki/Birthday_attack |
|
|
| Back to top |
|
|
|
| Fabrice... |
| Posted: Tue Sep 29, 2009 12:14 pm |
|
|
|
Guest
|
On Sep 29, 12:47 pm, Bipin <bipin.gau... at (no spam) gmail.com> wrote:
[quote:87cce4073e]Hi,please consider my novice question:
i was reading the Birthday problem in wikipedia
http://en.wikipedia.org/wiki/Birthday_problem
"In a group of at least 23 randomly chosen people, there is more than
50% probability that some pair of them will have the same birthday.
Such a result (for just 23 people, considering that there are 365
possible birthdays) is counter-intuitive to many. For 57 or more
people, the probability is more than 99%"
Question: So, to bruteforce a randomly choose 128 bit key, only 3.1 ×
10^19 random tries are necessary to find the key? (considering
birthday problem/attack)? [1] So, can birthday problem be used
effectively to find for a randomly choosen key, with random bruteforce
attack? Could this way be quicker than a full keyspace search with
bruteforce?
[/quote:87cce4073e]
What the chart means, i think, is that if you randomly generate
3.1x10^19 keys of 128bits, you have 75% probability to have at least 2
identical keys in your set.
It does NOT say that you have 75% probablity to find a second key
identical to the first key you generated (or any particular key).
To explain in term of birthday paradox, if you are in a room with 57
random people, you have 99% chance to find 2 people with the same
birthday, but NOT 99% chance of finding one with the same birthday as
you. |
|
|
| Back to top |
|
|
|
| Ilmari Karonen... |
| Posted: Tue Sep 29, 2009 4:24 pm |
|
|
|
Guest
|
On 2009-09-29, Bipin <bipin.gautam at (no spam) gmail.com> wrote:
[quote:c99000581c]Hi,please consider my novice question:
i was reading the Birthday problem in wikipedia
http://en.wikipedia.org/wiki/Birthday_problem
"In a group of at least 23 randomly chosen people, there is more than
50% probability that some pair of them will have the same birthday.
Such a result (for just 23 people, considering that there are 365
possible birthdays) is counter-intuitive to many. For 57 or more
people, the probability is more than 99%"
[/quote:c99000581c]
The important part in that description are the words "some pair".
Imagine that you're in a room with several other people. For the
probability of someone else in the room sharing *your* birthday to be
greater than one half, the number of people in the room must be at
least ln(2)*365, or about 253.
But to get a 50% chance of *any* two people sharing the same birthday,
you only need there to be that many possible *pairs* of people in the
room. Since N people can form N*(N-1)/2 possible pairs, you need only
23 people to get 253 pairs.
The birthday "paradox" is simply a consequence of the observation that
the number of possible pairs in a set of N elements is approximately
proportional to the square of N. That's all there is to it.
[quote:c99000581c]Question: So, to bruteforce a randomly choose 128 bit key, only 3.1 ×
10^19 random tries are necessary to find the key? (considering
birthday problem/attack)? [1] So, can birthday problem be used
effectively to find for a randomly choosen key, with random bruteforce
attack? Could this way be quicker than a full keyspace search with
bruteforce?
[/quote:c99000581c]
No. The birthday attack only works in the case where need to find a
pair of matching inputs, such as two strings that hash to the same
value, and you don't care what the inputs or the matching value are.
As soon as you fix a specific target (say, if you need to find a
string that hashes to some *given* value), it no longer helps.
--
Ilmari Karonen
To reply by e-mail, please replace ".invalid" with ".net" in address. |
|
|
| Back to top |
|
|
|
|
|
All times are GMT - 5 Hours
The time now is Fri Mar 19, 2010 4:19 am
|
|