Re: More about MT19937 in crypto

From: Gregory G Rose (ggr@qualcomm.com)
Date: 03/03/03 

From: ggr@qualcomm.com (Gregory G Rose)
Date: 2 Mar 2003 22:55:44 -0800

In article <3E62D5CE.9317B774@earthlink.net>,
Benjamin Goldberg <goldbb2@earthlink.net> wrote:
>Cristiano wrote:
>> But for cryptographic generator I think the speed is not the most
>> important thing.
>
>Untrue -- the reason Rijndael was chosen over the other 4 finalists was
>mainly due to it's speed.

I agree with Benjamin... speed is definitely the
name of the game in stream ciphers. They must be
secure first, but if they're slower than
counter-mode Rijndael the game is already over.

(Which is why I don't get this thread at all... a
precondition for being interested in the speed is
that you should have plausible belief in security,
which we don't have for MT unless you do
significant unproven things to it.)

>IMO, with a really well-designed variable-size-state generator, there
>should be two notable properties:
> 1/ When increasing the size of the state by N bits, this should
>increase the amount of work by a factor of 2**N.

A noble goal, which I believe is impossible. I
will ponder a proof of this. Basically, it's been
shown that no stream cipher can be as secure as
its total state, since there must be a
guess-and-determine attack that's at least one
bit better, and I think it might be possible to
show that you can't expand the state (without
changing anything else) perfectly exponentially
which would give a proof by induction.

> 2/ The time it takes to generate a bit of keystream should be O(N)
>with respect to the size of the state, though logarithmic or constant
>time would be better. In hardware, LFSRs (and MLS) operate in constant
>time wrt the size of the state.

No, it should be possible to do better than this.
Once the generator is initialised (which will by
definition take time proportional to the state)
any decent generator should chunk out output in
constant time. This is true of SNOW, SOBER, Turing
and SEAL (although I'm not sure of its decendent
SCREAM). Note, however, that the known attacks
against SNOW, SOBER and SCREAM do *not* scale with
the state; doubling the length of the shift
register adds at most an annoyance factor to the
attacks. (That's probably true of Turing too, but
it's too new to have any known attacks yet.)

Helix and Rijndael (in counter mode) are interesting counter
examples too, but in the other direction.
Increasing the state size for either would require
extra rounds to be added for security, and that
would affect both hardware and software
implementations.

BTW: a plug for Helix... I've concluded that it's
the most interesting new development in cipher
design for quite a while.

Greg. 

-- 
Greg Rose                                       INTERNET: ggr@qualcomm.com
Qualcomm Australia          VOICE:  +61-2-9817 4188   FAX: +61-2-9817 5199
Level 3, 230 Victoria Road,                http://people.qualcomm.com/ggr/ 
Gladesville NSW 2111    232B EC8F 44C6 C853 D68F  E107 E6BF CD2F 1081 A37C

Relevant Pages

  • Creating an open source packet generator
    ... I know this is a slightly odd request but it's for a project I'm working ... I have an IXIA packet generator which can ... The people who are performing these attacks are sourcing their IP's from ... type of free open source packet generator would be greatly appreciated. ...
    (comp.lang.ruby)
  • Re: LFSR and byte diffusion?
    ... are there efficient attacks against LFSR ... linear system of equations. ... LFSR-based stream ciphers if you go more ...
    (sci.crypt)
  • Re: newbie: please help...just your opinion
    ... > What kind of attacks are effective against this encryption algorithm? ... > pseudo random generator seeds does not reveal the plaintext, ... > function alone works as a small pseudo-random generator. ... Have you tried chosen plaintext attacks? ...
    (sci.crypt)
  • Re: New stream cipher algorithm, Adaptive Stream Cipher
    ... > What kind of a random number generator is this? ... cipher. ... Benjamin Choi ...
    (sci.crypt)
Quantcast