Cryptography-Digest Digest #51, Volume #14 Sat, 31 Mar 01 13:13:01 EST
Contents:
Re: simple stream cipher (hehehe) ("Tom St Denis")
Re: simple stream cipher (hehehe) ("Tom St Denis")
Re: DOES ANYONE HAVE "THE CODE BOOK" BY SIMON SINGH IN PDF FORMAT? PLZ POST OR
SEND - TIA! ("Tom St Denis")
Re: DOES ANYONE HAVE "THE CODE BOOK" BY SIMON SINGH IN PDF FORMAT? PLZ POST OR
SEND - TIA! (John Savard)
Re: simple stream cipher (hehehe) ("Tom St Denis")
Re: simple stream cipher (hehehe) ("Scott Fluhrer")
Blind signature ("Cristiano")
Re: simple stream cipher (hehehe) ("Tom St Denis")
Re: Idea - (LONG) (Mok-Kong Shen)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: simple stream cipher (hehehe)
Date: Sat, 31 Mar 2001 16:19:55 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9a4uca$6q1$[EMAIL PROTECTED]...
>
> Tom St Denis <[EMAIL PROTECTED]> wrote in message
> news:GZlx6.171921$[EMAIL PROTECTED]...
> > Take a LFSR (of multiple of 8-bits in len... 64-bits for example). Take
an
> > 8x8 transform that is one long single cycle convolution (i.e repeated
> calls
> > will cycle thru all values 0..255) that is also decently non-linear and
> > differentially well distributed.
> Why do you care about it being a convolution?
>
> >
> > To generate a byte of output do this
> >
> > 1. Clock the LFSR once (e.g new bit). Forget the output of the LFSR
> since
> > it's actually the state of the LFSR we care about.
> >
> > 2. Divide the LFSR into an array of bytes (starting with the lsb of
LFSR
> I
> > used the lfsr in galois mode for speed...)
> > 3. r <= 0
> > 4. for i = 0 to len_lfsr/8 do
> > 4.1 r <= sbox[LFSR[i] xor r]
> > 5. Output r
> >
> > It's somewhat fast, requires only 10 bytes of ram (8 for key, two for
loop
> > variables) and can be computed with a small piece of code.
> >
> > The way I see step 4.1 is as random 8x8 encryptions of "r". So
basically
> > you encrypt r eight times with diff parts of the LFSR. Since all of the
> > bytes of the LFSR change in each step the output isn't a single cycle of
> > 0..255.
> >
> > Any attacks? Obviously the last application of the sbox is not required
> > since it can be undone. So really it's 7 encryptions and 1 whitening.
> >
> > Another obvious attack is to simply guess the last lfsr byte. If you
get
> it
> > right you will know 7 of the 8 bits used in the next output byte. I
dunno
> > how you would use that...
> Well, I'm not sure if this will work out to a full attack (and I don't
have
> the time to work out all the details), but one approach might be a
> meet-in-the-middle attack:
>
> - Divide the LSFR into two equal halves, LFSR[0..3] and LFSR[4..7]
>
> - For LFSR[0..3], list for every LFSR contents the value of 'r' at
> iteration 4 of the loop for the next N bytes. Because you'll need to
assume
> the LSFR bits coming in, that should be 2**(32+N) possibilities, so you
> don't want to make N too large
>
> - For LFSR[4..7], list for every LFSR contents the mapping between the
value
> of 'r' at iteration 4 of the loop and the keystream output. Again,
because
> you'll need to assume the LFSR bits shifting in, that should be 2**(32+N)
> possibilities.
So the first step is to make an array of size [2^32] where (since you know
the input to the first half is zero) you want the output, then you make a
[256][2^32] table for the second step and compare to see??? Or do you start
guessing from the last part of the key and go upwards? I.e find all
KEY[4..7] that will make the output and then match them against all
KEY[0..3] that will make the output required for the first stage?
> Now, go through the lists, and search for items that are compatible (that
> is, jointly predict the correct keystream, and predicts the right bits
being
> shifted in). For each compatible set, run that set in the full cipher,
and
> see if it produces the correct keystream longterm. There'll be a lot of
> possibilities, but if you are able to pick N large enough so that there
are
> no more than 2**(32+N) of them (N=4 looks about right), then (assuming the
> search can be done efficiently, which is not immediately obvious), you
have
> an O(2**36) attack.
There will be alot of collisions since you can only use 8-bits of output to
suggest a key. The probability of guessing a key wrong is ??? (can't figure
this out off the top of my head).
Either way this requires about 2^32 + 2^40 bytes of memory which is very
unlikely.
Can't you break the attack even further? I.e divide it into four parts
KEY[0..1], KEY[2..3], etc.. and then precompute all possible outputs for
each stage? i.e you will have one [2^16] table and three [256][2^16] tables?
This would require only 2^16 + 3*2^24 bytes of ram and can be fully
precomputed before breaking a key.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: simple stream cipher (hehehe)
Date: Sat, 31 Mar 2001 16:24:21 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:GZlx6.171921$[EMAIL PROTECTED]...
I changed my cipher a bit..
> 1. Clock the LFSR once (e.g new bit). Forget the output of the LFSR
since
> it's actually the state of the LFSR we care about.
>
> 2. Divide the LFSR into an array of bytes (starting with the lsb of LFSR
I
> used the lfsr in galois mode for speed...)
> 3. r <= 0
This is the same.
> 4. for i = 0 to len_lfsr/8 do
> 4.1 r <= sbox[LFSR[i] xor r]
> 5. Output r
Here I changed it so that I do
4. For i = 0 to (len_lfsr/8)-1 do
4.1 r <= sbox[LFSR[i] xor r]
5. output r xor sbox[LFSR[len_lfsr/8]]
The idea is that there is no undoable "encryption" done and that the last
"whitening" step is done by sending the key thru the non-linear sbox.
I think your original attack (poncho) will still apply though...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: DOES ANYONE HAVE "THE CODE BOOK" BY SIMON SINGH IN PDF FORMAT? PLZ POST
OR SEND - TIA!
Date: Sat, 31 Mar 2001 16:35:10 GMT
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> On Fri, 30 Mar 2001 20:35:47 GMT, "Tom St Denis" <[EMAIL PROTECTED]>
wrote:
>
> >
> >"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >> "George T. Chambers Jr." wrote:
> >> > Does anyone have "The Code Book" by Simon Singh in PDF format? Plz
> >> > post or send! - TIA!
> >>
> >> Please don't!
> >
> >Nothing like open piracy to reaffirm my believe in losers using the
internet
> >... hehehehe
> >
> >Tom
> >
> >
>
> For one thing, it's not piracy. Two: Your're an asshole!
>
Because I openly admit I despise piracy? Sure then I am an asshole.
Tom
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: DOES ANYONE HAVE "THE CODE BOOK" BY SIMON SINGH IN PDF FORMAT? PLZ POST
OR SEND - TIA!
Date: Sat, 31 Mar 2001 16:20:06 GMT
On Fri, 30 Mar 2001 21:03:19 GMT, [EMAIL PROTECTED] wrote, in
part:
>For one thing, it's not piracy. Two: Your're an asshole!
Since when has the copyright on "The Code Book" by Simon Singh expired
or been invalidated? Of course it's piracy when unauthorized copies
are made of any copyrighted work. Whether or not money changes hands
is irrelevant.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: simple stream cipher (hehehe)
Date: Sat, 31 Mar 2001 16:33:39 GMT
> Here I changed it so that I do
>
> 4. For i = 0 to (len_lfsr/8)-1 do
> 4.1 r <= sbox[LFSR[i] xor r]
> 5. output r xor sbox[LFSR[len_lfsr/8]]
>
> The idea is that there is no undoable "encryption" done and that the last
> "whitening" step is done by sending the key thru the non-linear sbox.
>
> I think your original attack (poncho) will still apply though...
The break actually requires about "2^16 + (lfsr_len/8 - 1)2^24" memory and
"256^(lfsr_len / 16)" work. Since if you group the lfsr by two bytes you
will find 256 possible 16-bit keys for each known output for each stage.
Only one of the 256 is correct so you will end up with 256^n suggested keys.
In the case of a 64-bit key would will end up with 2^32 suggested keys and
you can either exhaustive search it or use more plaintexts. For an 80-bit
key you will end up with 2^40 suggested keys... (i.e 2^(n/2)). So you need
a 192-bit LFSR to provide some decent security (3x slower...) to provide
2^96 "security". The space requirement would be at least 385,941,504 bytes
for the tables and negible for the rest since you can just test suggested
keys instantly.
I have implemented this on an 8051 in C (I do C first then asm ...) and with
an 80-bit lfsr it outputs at about 4800 baud. The C code is terribly
inefficient since it doesn't alias with registers and it promotes all
"unsigned char" to unsigned's for accessing arrays. A pure asm copy would
be about 5x faster since it's not that complicated.
Hmm.. well with a 192-bit LFSR I am guessing it will be able to output
somewhere around 12kbit a second (on the 8051) if I use every trick I know
of to optimize the code. That meets the speed of the average block cipher
on the same cpu...
Tom
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: simple stream cipher (hehehe)
Date: Sat, 31 Mar 2001 08:38:44 -0800
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:Lsnx6.172753$[EMAIL PROTECTED]...
>
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:9a4uca$6q1$[EMAIL PROTECTED]...
> >
> > Tom St Denis <[EMAIL PROTECTED]> wrote in message
> > news:GZlx6.171921$[EMAIL PROTECTED]...
> > > Take a LFSR (of multiple of 8-bits in len... 64-bits for example).
Take
> an
> > > 8x8 transform that is one long single cycle convolution (i.e repeated
> > calls
> > > will cycle thru all values 0..255) that is also decently non-linear
and
> > > differentially well distributed.
> > Why do you care about it being a convolution?
> >
> > >
> > > To generate a byte of output do this
> > >
> > > 1. Clock the LFSR once (e.g new bit). Forget the output of the LFSR
> > since
> > > it's actually the state of the LFSR we care about.
> > >
> > > 2. Divide the LFSR into an array of bytes (starting with the lsb of
> LFSR
> > I
> > > used the lfsr in galois mode for speed...)
> > > 3. r <= 0
> > > 4. for i = 0 to len_lfsr/8 do
> > > 4.1 r <= sbox[LFSR[i] xor r]
> > > 5. Output r
> > >
> > > It's somewhat fast, requires only 10 bytes of ram (8 for key, two for
> loop
> > > variables) and can be computed with a small piece of code.
> > >
> > > The way I see step 4.1 is as random 8x8 encryptions of "r". So
> basically
> > > you encrypt r eight times with diff parts of the LFSR. Since all of
the
> > > bytes of the LFSR change in each step the output isn't a single cycle
of
> > > 0..255.
> > >
> > > Any attacks? Obviously the last application of the sbox is not
required
> > > since it can be undone. So really it's 7 encryptions and 1 whitening.
> > >
> > > Another obvious attack is to simply guess the last lfsr byte. If you
> get
> > it
> > > right you will know 7 of the 8 bits used in the next output byte. I
> dunno
> > > how you would use that...
> > Well, I'm not sure if this will work out to a full attack (and I don't
> have
> > the time to work out all the details), but one approach might be a
> > meet-in-the-middle attack:
> >
> > - Divide the LSFR into two equal halves, LFSR[0..3] and LFSR[4..7]
> >
> > - For LFSR[0..3], list for every LFSR contents the value of 'r' at
> > iteration 4 of the loop for the next N bytes. Because you'll need to
> assume
> > the LSFR bits coming in, that should be 2**(32+N) possibilities, so you
> > don't want to make N too large
> >
> > - For LFSR[4..7], list for every LFSR contents the mapping between the
> value
> > of 'r' at iteration 4 of the loop and the keystream output. Again,
> because
> > you'll need to assume the LFSR bits shifting in, that should be
2**(32+N)
> > possibilities.
Actually, what I should have said is that you take the N bytes of known
keystream, and run the cipher backwards for 4 iterations, obtaining the
value of that 'r' at iteration 4 must be in order to generate the known
keystream. This makes the searching phase to a simple 'sort-and-match', and
also reduces the memory each guess takes. Doh!
>
> So the first step is to make an array of size [2^32] where (since you know
> the input to the first half is zero) you want the output, then you make a
> [256][2^32] table for the second step and compare to see??? Or do you
start
> guessing from the last part of the key and go upwards? I.e find all
> KEY[4..7] that will make the output and then match them against all
> KEY[0..3] that will make the output required for the first stage?
>
> > Now, go through the lists, and search for items that are compatible
(that
> > is, jointly predict the correct keystream, and predicts the right bits
> being
> > shifted in). For each compatible set, run that set in the full cipher,
> and
> > see if it produces the correct keystream longterm. There'll be a lot of
> > possibilities, but if you are able to pick N large enough so that there
> are
> > no more than 2**(32+N) of them (N=4 looks about right), then (assuming
the
> > search can be done efficiently, which is not immediately obvious), you
> have
> > an O(2**36) attack.
>
> There will be alot of collisions since you can only use 8-bits of output
to
> suggest a key. The probability of guessing a key wrong is ??? (can't
figure
> this out off the top of my head).
Well, I use N*8 bits. Assuming that, I would expect the searching phase to
find about 2**(64-8*N) possible keys, and the real one will be in there
somewhere. These are all the keys that generate that initial N byte initial
segment. I assume that I actually have more than N bytes of keystream, but
I'm using only the first N during the initial search. Then, to find the
real one, I just try them all out, and find which one generates all the
keystream I know about. This should take O(2**(64-8*N)) time.
>
> Either way this requires about 2^32 + 2^40 bytes of memory which is very
> unlikely.
Actually, that's not too unlikely if you happen to have a tape. And, with
my correction above, it's more like O(2^32) memory.
However, one other thing I misunderstood about your cipher was that I
assumed that, every time you stepped the LFSR, you clocked it one bit. It's
far more likely that you clock it an entire byte. This increases the number
of shifted-in LFSR bits you have to guess, and a back-of-the-envelope
calculation shows that this makes this attack about O(2**48) work -- better
than brute force, but not drastically.
>
> Can't you break the attack even further? I.e divide it into four parts
> KEY[0..1], KEY[2..3], etc.. and then precompute all possible outputs for
> each stage? i.e you will have one [2^16] table and three [256][2^16]
tables?
> This would require only 2^16 + 3*2^24 bytes of ram and can be fully
> precomputed before breaking a key.
The problem with that is I have no idea how you'd do the search. The nice
thing about breaking it up into precisely two is that you can take your two
lists, sort them, and then sequentially scan them for matches in the
internal 'r' values. I have no idea how to generalize this concept for 3 or
more lists.
--
poncho
------------------------------
From: "Cristiano" <[EMAIL PROTECTED]>
Subject: Blind signature
Date: Sat, 31 Mar 2001 18:58:48 +0200
How can I implement blind signature with elliptic curves?
Thanks
Cristiano
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: simple stream cipher (hehehe)
Date: Sat, 31 Mar 2001 17:06:33 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9a51pq$hhl$[EMAIL PROTECTED]...
> However, one other thing I misunderstood about your cipher was that I
> assumed that, every time you stepped the LFSR, you clocked it one bit.
It's
> far more likely that you clock it an entire byte. This increases the
number
> of shifted-in LFSR bits you have to guess, and a back-of-the-envelope
> calculation shows that this makes this attack about O(2**48) work --
better
> than brute force, but not drastically.
No I clock it one bit only. (for speed issues obviously).
> >
> > Can't you break the attack even further? I.e divide it into four parts
> > KEY[0..1], KEY[2..3], etc.. and then precompute all possible outputs for
> > each stage? i.e you will have one [2^16] table and three [256][2^16]
> tables?
> > This would require only 2^16 + 3*2^24 bytes of ram and can be fully
> > precomputed before breaking a key.
> The problem with that is I have no idea how you'd do the search. The nice
> thing about breaking it up into precisely two is that you can take your
two
> lists, sort them, and then sequentially scan them for matches in the
> internal 'r' values. I have no idea how to generalize this concept for 3
or
> more lists.
Well my attack works like this.
You make the first table which is [256][256] for all possible keys (since
the input is 0 to the first round) where the table gives the output after
the first two rounds. Then you make N more [256][256][256] tables that for
every possible input to this pair of rounds and every possible key
combination. Let's say there are four rounds (just for example, e.g four
byte LFSR). Given a keystream byte 'X' you look in the last[][][] table to
see which elements output a 'X'. There will be 256 matches in the key
portion (and 256 matches for the input part). Then for every possible input
to the third round you have the two last bytes of the key. You simply hold
the input into the third round as true (assume it) and attack the first two
rounds recursively. You then get 256 suggest keys their (2^16 in total so
far). You try them all. If none of them are the key then you go back to
the third round and assume the input was something else. The attack effort
is 2^24 and this requires 24MB of ram.
To generalize this. For a N-Byte LFSR you need 2^16 + (N/2 - 1)2^24 bytes
of memory and the attack work is 2^(N/2)8) * 2^((N/2 - 1)8) = 2^(8N - 8).
So my attack is only 256 times faster then brute force but unlike your
attack doesn't require nearly as much memory.
I could make my attack work by dividing into halves by simply doing (say for
N=8) a [256][256][256][256] table for the first halve where you compute the
output, then you compute a [256][256][256][256][256] table for all inputs
and all keys. Then you simply search the second half to look for all keys
that give the output you want. 2^24 will, you guess the input then match the
first half and guess the key. That's 2^56 work again... arrg... so my
attack doesn't work well at all..
Can you explain your attack more concisely please?
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Idea - (LONG)
Date: Sat, 31 Mar 2001 19:24:03 +0200
Rob Warnock wrote:
>
[snip]
> Is there some way to quantify the added "work" for each primitive
> operation (as a function of, "k", "m", how the bits & substitutions &
> permutations are chosen, existing redundancy of the text at each step,
> etc.), as well as assign an "increase in work" to the *composition* of
> such primitives[*], so that (in theory) one could start from the identity
> transformation and proceed stepwise all the way up to (say) Rijndael
> (or the like), thereby quantifying the total "work" that has been
> introduced? If so, this might be a basis for a formal discipline of
> cipher design.
If one has r bits of truly random bits (never mind how to
get this), one can only encrypt r bits with perfect
security in the sense of Shannon. Encrypting n (n>r) bits
can be 'practically' (though not perfectly) secure due to
the limited available resources of the opponent. But that
is also essentially dependent on the 'qualtity' of the
encryption algorithm (either 'block' or 'stream'). One
can't rigorously define, let alone measure, that 'quality',
much the same as one can't scientifically evaluate
paintings, architectures, etc. etc. That's a problem that
is inherently unsolvable in my conviction. Subjectivity
in crypto is there to stay.
M. K. Shen
==========================
http://home.t-online.de/home/mok-kong.shen
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
