How do you determine how many guesses an attacker would need to guess a key or keystream? (stream ciphers)
in [Cryptography]
|
Prev: Need help
Next: How do you determine how many guesses an attacker would need toguess a key or keystream? (stream ciphers)
From: mark on 23 Jan 2010 12:04 Sorry for the newbie question. What difference would it make for an attacker with respect to trying to guess an input key into a stream cipher, versus trying to guess the outputted keystream? If you put a key into some stream cipher, it may use several LFSR's to help encrypt your message. Assuming something like the E0 cipher (but not limited to that cipher) (http://en.wikipedia.org/wiki/E0_%28cipher %29), how do they impact whether it is smarter to guess a key versus a keystream? Thanks :)
From: mark on 23 Jan 2010 13:47 On Jan 23, 12:41 pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: > On 2010-01-23, mark <cheesemonke...(a)gmail.com> wrote: > > > Sorry for the newbie question. What difference would it make for an > > attacker with respect to trying to guess an input key into a stream > > cipher, versus trying to guess the outputted keystream? > > > If you put a key into some stream cipher, it may use several LFSR's to > > help encrypt your message. Assuming something like the E0 cipher (but > > not limited to that cipher) (http://en.wikipedia.org/wiki/E0_%28cipher > > %29), how do they impact whether it is smarter to guess a key versus a > > keystream? > > Since the keystream is typically longer than the key, it is harder to > guess. also, you have no criteria for deciding whether you have guessed > the right stream or not (See One Time Pad and its proof of security). > > > > > Thanks :) How does the use of LFSRs play into this, though? If you determine the key, you still need to know the nature and the state of the LFSRs in order to generate useful keystream frames to encrypt/decrypt messages, correct? In the case of the e0 cipher, there are 4 LFSRs, along with a 128 bit key and some other information passed to the cipher. I think I'm missing a key piece of knowledge here :) Bruteforcing on a 128 bit key would require at most 2^128 guesses. The e0 cipher creates a keystream frame of approximately 3000 bits. We will be getting a different keystream with each frame. So, does this mean that attacking a keystream would be approximately 2^3000 (at most. expected half of that) guesses for each keystream, and cracking that is only useful for a short period of time, until we get a new frame?
From: Greg Rose on 23 Jan 2010 16:20 In article <3d75bccb-bf7e-4b3a-a371-6d1b101a20be(a)22g2000yqr.googlegroups.com>, mark <cheesemonkey22(a)gmail.com> wrote: >Sorry for the newbie question. What difference would it make for an >attacker with respect to trying to guess an input key into a stream >cipher, versus trying to guess the outputted keystream? > >If you put a key into some stream cipher, it may use several LFSR's to >help encrypt your message. Assuming something like the E0 cipher (but >not limited to that cipher) (http://en.wikipedia.org/wiki/E0_%28cipher >%29), how do they impact whether it is smarter to guess a key versus a >keystream? You can't guess the keystream, since the bits appear independent of each other. Even more, you should assume known plaintext attacks, where the attacker knows both the input and output, and hence can *derive* the keystream for at least large segments of generated output. So, really, if you are guessing something it should be the key. Another alternative is to guess the internal state of the generator; this may be much more efficient than guessing the key and doing all the key setup, and you might be able to guess just some of it and derive the rest (so called "Guess and Determine attack"). Once you know the internal state it is often possible to work backward to the actual key, or even if not, you can generate more output. Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
From: Greg Rose on 23 Jan 2010 16:23
In article <65e5a47f-3393-4d7b-a171-43b50926aeb0(a)h2g2000yqj.googlegroups.com>, mark <cheesemonkey22(a)gmail.com> wrote: >On Jan 23, 12:41�pm, unruh <un...(a)wormhole.physics.ubc.ca> wrote: >> On 2010-01-23, mark <cheesemonke...(a)gmail.com> wrote: >> >> > Sorry for the newbie question. �What difference would it make for an >> > attacker with respect to trying to guess an input key into a stream >> > cipher, versus trying to guess the outputted keystream? >> >> > If you put a key into some stream cipher, it may use several LFSR's to >> > help encrypt your message. �Assuming something like the E0 cipher (but >> > not limited to that cipher) (http://en.wikipedia.org/wiki/E0_%28cipher >> > %29), how do they impact whether it is smarter to guess a key versus a >> > keystream? >> >> Since the keystream is typically longer than the key, it is harder to >> guess. also, you have no criteria for deciding whether you have guessed >> the right stream or not (See One Time Pad and its proof of security). >> >> >> >> > Thanks :) > >How does the use of LFSRs play into this, though? If you determine >the key, you still need to know the nature and the state of the LFSRs >in order to generate useful keystream frames to encrypt/decrypt >messages, correct? In the case of the e0 cipher, there are 4 LFSRs, >along with a 128 bit key and some other information passed to the >cipher. I think I'm missing a key piece of knowledge here :) >Bruteforcing on a 128 bit key would require at most 2^128 guesses. >The e0 cipher creates a keystream frame of approximately 3000 bits. > >We will be getting a different keystream with each frame. So, does >this mean that attacking a keystream would be approximately 2^3000 (at >most. expected half of that) guesses for each keystream, and cracking >that is only useful for a short period of time, until we get a new >frame? So, you can either guess the 3000 bits of keystream, or you can guess something else that is 3000 bits long, namely the contents of the frame itself. The time to guess, the probability of correctness, and the ease of guessing the wrong thing, are all the same. Greg. -- Greg Rose 232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C |