Re: Can birthday problem be applied in bruteforce
- From: Ilmari Karonen <usenet2@xxxxxxxxxxxxxx>
- Date: 29 Sep 2009 22:24:12 GMT
On 2009-09-29, Bipin <bipin.gautam@xxxxxxxxx> wrote:
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%"
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.
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?
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.
.
- References:
- Can birthday problem be applied in bruteforce
- From: Bipin
- Can birthday problem be applied in bruteforce
- Prev by Date: Re: Can birthday problem be applied in bruteforce
- Next by Date: Re: SET vs. SEQUENCE when there's only one component
- Previous by thread: Re: Can birthday problem be applied in bruteforce
- Next by thread: Authenticating variables size payloads with RSA
- Index(es):
Relevant Pages
|
