Cryptography-Digest Digest #665, Volume #9 Sat, 5 Jun 99 16:13:02 EDT
Contents:
Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing) (Boris
Kazak)
Re: Function Feedback Registers (David Wagner)
Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing) (Boris
Kazak)
Re: what cipher? (David Wagner)
Re: what cipher? (Boris Kazak)
Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing) (Boris
Kazak)
Re: Challenge to SCOTT19U.ZIP_GUY ([EMAIL PROTECTED])
Re: Function Feedback Registers ([EMAIL PROTECTED])
Re: Challenge to SCOTT19U.ZIP_GUY (SCOTT19U.ZIP_GUY)
Re: Challenge to SCOTT19U.ZIP_GUY (SCOTT19U.ZIP_GUY)
Re: Challenge to SCOTT19U.ZIP_GUY (SCOTT19U.ZIP_GUY)
Re: what cipher? (Terry Ritter)
----------------------------------------------------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing)
Date: Sat, 05 Jun 1999 10:23:49 -0400
Reply-To: [EMAIL PROTECTED]
Paul Onions wrote:
>
> If I understand your description correctly then your hash
> is not collision-resistant.
>
> If I have two files that differ in only the first 4 bytes
> such that the XOR of these bytes is the same then they will
> both hash to the same value.
>
> e.g. given file A then construct file B to be the same as
> file A but with the order of the first two bytes swapped.
====================
In this case you will select the same multiplier from the table,
but since multiplicand (mod 2^32+1+) is different (swapped bytes),
the product and all the subsequent hash will be different.
=======================
>
> BTW I tried to test this with your source but it unfortunately
> core dumped with a segmentation fault when I tried to run it.
> (I use Linux. FYI it crashed after it asked me for the input
> filename but before it produced an output file).
=========================
Sorry, it is entirely probable that the file access functions or
(also possible) string functions which handle file names in
LINUX have some subtle differences from their Win98 counterparts.
I cannot help you here, I don't have LINUX installed yet on my
computer. BTW, you are free to revise ALL the source code as you see
fit for your needs.
=========================
>
> Please correct me if my understanding is wrong.
> Paul(o)
>
> --
> Paul Onions [EMAIL PROTECTED]
> PGP 2.6.3 key available
> D704688BEFBF2D5D 546BC1D603E2A8E0
Best wishes BNK
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Function Feedback Registers
Date: 5 Jun 1999 10:15:22 -0700
The usual formulation is as a NLFSR (non-linear feedback shift register).
It computes a one-bit function f(S) on the n-bit state of the register,
shifts the register right, and puts f(S) in the high bit (bit n-1), so
that the new state is S' = (S>>1) | (f(S) << (n-1)) in C notation.
One important design principle (but not the only one) for a NLFSR is to
ensure that the stepping transformation is reversible. (In other words,
you don't want two states to have the same successor, because that loses
information.) One way to guarantee this property is to use an f of the
form f(S) = (S&1) ^ g(S>>1). (Do you see why? It is an easy exercise to
demonstate how to reverse the stepping transformation of a NLFSR with f
of this form.)
Not much seems to be known in the open literature about the design of
secure NLFSR's.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing)
Date: Sat, 05 Jun 1999 10:33:19 -0400
Reply-To: [EMAIL PROTECTED]
Paul Onions wrote:
>
> Paul Onions wrote:
> >
> > Paul Onions wrote:
> > >
> > > If I understand your description correctly then your hash
> > > is not collision-resistant.
> > >
> > > If I have two files that differ in only the first 4 bytes
> > > such that the XOR of these bytes is the same then they will
> > > both hash to the same value.
> >
> > Ooops! That is nonsense, sorry.
> >
> > I really should learn to sit on my hands for 5 minutes
> > before hitting that send key!
>
> On the other hand, maybe I was on the right track after all...
>
> Given two messages that differ in only their first 4 bytes then
> it seems possible that the result of the first multiplication could
> be the same in both cases and so will result in the same hash.
======================
Actually it would require about 2^31 multiplications, you just take
the first 4 bytes and do the multiplication selecting the multiplier
from the table. It is probable that with another bytes (and another
multiplier) you will come to the same product.
BTW, this is where IV comes in very handy.
You are correct, this is a definite flaw in the sense of
collision-resistance.
========================
>
> Please feel free to point and laugh if I'm talking nonsense again!
>
> (okay, 2 minutes on the hands, that should be enough... :-)
>
> Paul(o)
>
> --
> Paul Onions [EMAIL PROTECTED]
> PGP 2.6.3 key available
> D704688BEFBF2D5D 546BC1D603E2A8E0
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: what cipher?
Date: 5 Jun 1999 10:27:55 -0700
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> [...] we drop plaintext into the SR, step it for a while, then
> use the result as ciphertext. I would call that a form of block
> cipher. The article implies that the keying is the step count, and
> fortunately with a LFSR we do have fast ways to step. It also implies
> that we have a keying register, which we step enough to diffuse the
> key and each value we take, then use those values to indicate how much
> we step the cipher register.
Sounds like an intriguing design, following a different path than any
other system I've seen. Thanks for posting the high-level description!
Since you looked at the article, would you mind if I ask a few questions?
1. Is this used one-bit-at-a-time (drop a plaintext bit in, step, repeat)
or do you drop in the entire plaintext (or at least as much will fit in
the register) all at once?
2. Is the output one bit from the main register, or is the entire contents
of the register?
3. How on earth do you decrypt?? :-)
> Now, I've never tried to recover LFSR
> step distance knowing initial and resulting values, and with multiple
> registers that sounds tough.
Here's an observation: if you know the entire contents of the register
before and after the stepping, and you know the taps, then recovering
the step distance (for a n-bit LFSR) is just a discrete log problem over
GF(2^n).
Thus, you can solve it for any stepping distance if n is not too large
(<512 or 1024 or so). Also, if the step amount is known to be relatively
small, say less than 2^m, then you can solve the discrete log problem
with 2^{m/2} operations using a birthday algorithm.
It seems like a harder problem if you only know part of the initial
and/or final register state. (Use linear consistency checks, maybe?)
And I have absolutely no clue about how one might proceed if the taps
are unknown.
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: what cipher?
Date: Sat, 05 Jun 1999 11:00:20 -0400
Reply-To: [EMAIL PROTECTED]
David Wagner wrote:
>
> In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> > [...] we drop plaintext into the SR, step it for a while, then
> > use the result as ciphertext. I would call that a form of block
> > cipher. The article implies that the keying is the step count, and
> > fortunately with a LFSR we do have fast ways to step. It also implies
> > that we have a keying register, which we step enough to diffuse the
> > key and each value we take, then use those values to indicate how much
> > we step the cipher register.
>
> Sounds like an intriguing design, following a different path than any
> other system I've seen. Thanks for posting the high-level description!
>
> Since you looked at the article, would you mind if I ask a few questions?
>
> 1. Is this used one-bit-at-a-time (drop a plaintext bit in, step, repeat)
> or do you drop in the entire plaintext (or at least as much will fit in
> the register) all at once?
> 2. Is the output one bit from the main register, or is the entire contents
> of the register?
> 3. How on earth do you decrypt?? :-)
>
(snip)
====================
Actually, courtesy of Lars Knudsen, I published a desciption of a
similar cipher in his "Journal of Craptology" (the publisher's
comment was "It is a really crappy paper, indeed, obviously
resulting from eating an excess amount of magical mushrooms").
The title is "Drunken family", the idea of the cipher boils
down to a shift register with the mixing function being modular
multiplication, you could call it MFSR - Multiplicative Feedback
Shift Register. It is not presented this way in the paper, there
the register is stationary and the multiplier moves along the
register, but this is a superficial difference.
Decryption uses the same operation, with inverses instead of
modular multipliers, and the register shifting backwards.
If the Journal is still online, you are welcome. Sorry, I don't
have yet a Web page.
Best wishes BNK
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Subject: Re: Finding a 192 bit hash (Was: Using symmetric encryption for hashing)
Date: Sat, 05 Jun 1999 11:22:13 -0400
Reply-To: [EMAIL PROTECTED]
Paul Onions wrote:
>
> Paul Onions wrote:
> >
> > Paul Onions wrote:
> > >
> > > If I understand your description correctly then your hash
> > > is not collision-resistant.
> > >
> > > If I have two files that differ in only the first 4 bytes
> > > such that the XOR of these bytes is the same then they will
> > > both hash to the same value.
> >
> > Ooops! That is nonsense, sorry.
> >
> > I really should learn to sit on my hands for 5 minutes
> > before hitting that send key!
>
> On the other hand, maybe I was on the right track after all...
>
> Given two messages that differ in only their first 4 bytes then
> it seems possible that the result of the first multiplication could
> be the same in both cases and so will result in the same hash.
>
> Please feel free to point and laugh if I'm talking nonsense again!
>
> (okay, 2 minutes on the hands, that should be enough... :-)
>
> Paul(o)
>
> --
> Paul Onions [EMAIL PROTECTED]
> PGP 2.6.3 key available
> D704688BEFBF2D5D 546BC1D603E2A8E0
======================
Actually, it would be much safer (and simpler) to use one single
multiplier, or, for paranoids, change the multiplier once every round.
In this case different bytes will always yield a different product.
The old adage KISS (Keep It Simple, Stupid!) is still true...
The 256-enrty table will be excessive, the code will run faster.
Any suggestions on the multipliers?
Thanks and best wishes BNK
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Sat, 05 Jun 1999 17:51:14 GMT
>
> The other version can still be there as the 'fully optimized'
implementation.
Sure. Well let's see it's dang slow. It would take a miracle to make
it at least 3 times as *slow* as Blowfish (or similar). It also
requires a lot of memory, and key material. Which suggests poor use of
available resources, and bad key management. Smaller keys are not
always worst, and you have to realize that. A key of 128 bits where
the entire key is used effective will require on average 2^127 trials
to break (unless the cipher has some exploitable weakness).
I would suggest that he actually gives out the guidelines for the
design criterion, so that it can be fully optimized. Maybe we can use
a similar idea with say lots less key/memory requirements. The use of
19 bit words is not a good idea. Maybe 19 bit inputs into a 19x32 sbox
or something. But this would be a rather large s-box, unless it was
derived with some sequence (geometric/arithmetic...).
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Function Feedback Registers
Date: Sat, 05 Jun 1999 18:23:56 GMT
> The usual formulation is as a NLFSR (non-linear feedback shift
register).
> It computes a one-bit function f(S) on the n-bit state of the
register,
> shifts the register right, and puts f(S) in the high bit (bit n-1), so
> that the new state is S' = (S>>1) | (f(S) << (n-1)) in C notation.
Well this is similar except there are n functions being used. Each
segment (or cell) of the state is not permutated using the same
function. And if the cycle length is exactly 2^bn (b bits per word,
and n words) then it should be arguable that it's reversible.
>
> One important design principle (but not the only one) for a NLFSR is
to
> ensure that the stepping transformation is reversible. (In other
words,
> you don't want two states to have the same successor, because that
loses
> information.) One way to guarantee this property is to use an f of
the
> form f(S) = (S&1) ^ g(S>>1). (Do you see why? It is an easy
exercise to
> demonstate how to reverse the stepping transformation of a NLFSR with
f
> of this form.)
Well if two states have the same successor the cycle length is not
maximal is it? And I wouldn't imagine how any function could create to
outputs from one input.
>
> Not much seems to be known in the open literature about the design of
> secure NLFSR's.
>
Hmm, well I seriously doubt that I (currently) am the person to really
frontier this. It was but a mere idea.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
Sent via Deja.com http://www.deja.com/
Share what you know. Learn what you don't.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Sat, 05 Jun 1999 20:15:05 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>Tim Redburn wrote:
>>
>> On Fri, 04 Jun 1999 20:24:05 GMT, [EMAIL PROTECTED]
>> (SCOTT19U.ZIP_GUY) wrote:
>>
>> >
>> > I have worked on many aircraft simulations and OFP;s one of the main
>> >problems that seems to occur over and over is that other people keep
>> >missing the obvious errors in the code becasue most people inheirently
>> >put faith on the comments and this leads to major maistakes that take
>> >years to find and fix.
>>
>> Quite the opposite. Comments tell you what the programmer intended.
>> It is then easier then to verify that the code actually works
>> as intended. If you don't know what the code was meant to do, how can
>> you debug it ?
>
>Actually it's harder than that. Comments often tell you what the
>_original_ programmer _originally_ intended. The secret to good writing
>(of any kind) is rewriting. Rewriting implies that the intentions of
>the author evolve during the process. Thus the final intentions of the
>author(s) may be arbitrarily far from the original intentions.
>
>A truism of software maintenance (which is mostly software analysis) is
>that the value of comments is often negative. More often than not. The
>cost of persuing a false trail based on the comments is high. It can
>pollute your concept pool long after you've learned better (holographic
>memory effects I suppose).
>
>ThHis explains one of the first rules of maintenance. Delete the
>comments, then study the code. Review the comments (skeptically) later
>to resolve problems and find issues warnings not apparent from the code.
>
>The Grail of good software is self-documenting code. That does NOT mean
>comments.
You write good and seem practical. I think you may have worked years
with other peoples code like I have.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Sat, 05 Jun 1999 20:13:34 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] wrote:
>SCOTT19U.ZIP_GUY wrote:
>>
>> In article <[EMAIL PROTECTED]>, Geoff Thorpe <[EMAIL PROTECTED]>
> wrote:
>> >Hi there,
>> >
>> >Hey, he writes poor code. He refuses to adequately document his own
>> >"techniques" (the mindless accusations that only stupid people don't
>>
>> Only a few think the coding is poor.
>
>How many think the coding is great? I have yet to see one.
>
>> I don't have to follow rules
>
>You should have terminated this sentance at this point.
>
>> that others blindly follow. And the code is full of many comments. But
>> it should be clear to any one who has a working knowledge of C and
>> some baiscs of how a PC works. Yes I don't make every one happy
>> that would be an impossible job.
>
>Try making one person barely satisfied. Until you have done that you
>risk being accused of bad faith. I.e., you aren't really trying.
>
I did that with Horst Ossifrage and actually did it with Mok but I think he
was faking interest. Actually I am anwsering Redburn questions and if Paul
Onions has any or Joe P.
>Pick someone, anyone, and answer their questions honestly. Do what they
>ask in terms of clarifying your code. It won't make the code worse. I
>promise.
>
>>
>> David A. Scott
>> --
>> SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
>> http://www.jim.com/jamesd/Kong/scott19u.zip
>> http://members.xoom.com/ecil/index.htm
>> NOTE EMAIL address is for SPAMERS
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Challenge to SCOTT19U.ZIP_GUY
Date: Sat, 05 Jun 1999 20:41:39 GMT
In article <7jbk7k$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Frank Gifford)
wrote:
>In article <[EMAIL PROTECTED]>,
>Tim Redburn <[EMAIL PROTECTED]> wrote:
>>...
>>Even if you have personal objections to that style, why wont
>>you put your objections to one side and keep everybody
>>happy by writing scott19u.zip in that style.
>>...
>
>Actually, I would recommend that David create a separate version of the
>program which is functionally identical. It would have comments about why
>things are done a certain way, a nicer way that arrays are accessed on 19
>bit boundaries, etc. Even if this means the new version takes ten times
>longer to run, it would be enough for people to walk through the code and
Like I said to even compile 19u I needed my sons machine. However if
one has a nicer way of overlaying memory with a 19bit arrays. such that
it starts at a byte boudary and also a bit boundary 9 bits earlier I could
make an attempt. I have to admit to me this was the hardest concept to
make the C code work on there 19bit fields. If the code here is confusing
how do you ivory tower types do this.
I feel this is a straight forward question do any of you have an anwser
or is this something that C pureists think should not every be done.
>test it. After all, right now, people are interested in testing the security
>of the algorithm.
They still have working code. Many tests can be done using the
executables.
>
>The other version can still be there as the 'fully optimized' implementation.
>
>-Giff
>
>
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
http://members.xoom.com/ecil/index.htm
NOTE EMAIL address is for SPAMERS
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: what cipher?
Date: Sat, 05 Jun 1999 19:52:33 GMT
On 5 Jun 1999 10:27:55 -0700, in
<7jbmmr$3ic$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David Wagner) wrote:
>In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>> [...] we drop plaintext into the SR, step it for a while, then
>> use the result as ciphertext. I would call that a form of block
>> cipher. The article implies that the keying is the step count, and
>> fortunately with a LFSR we do have fast ways to step. It also implies
>> that we have a keying register, which we step enough to diffuse the
>> key and each value we take, then use those values to indicate how much
>> we step the cipher register.
>
>Sounds like an intriguing design, following a different path than any
>other system I've seen. Thanks for posting the high-level description!
>
>Since you looked at the article, would you mind if I ask a few questions?
The article is written in a sort of handwavy style which is probably
easy to interpret if one has worked on such a system.
>1. Is this used one-bit-at-a-time (drop a plaintext bit in, step, repeat)
> or do you drop in the entire plaintext (or at least as much will fit in
> the register) all at once?
I think they are talking about tossing a block of text in the register
and then scrambling.
>2. Is the output one bit from the main register, or is the entire contents
> of the register?
I think they are talking about taking the whole thing.
>3. How on earth do you decrypt?? :-)
The main way they mention is to find involutory transformations. I'm
surprised they exist, but I generally find them questionable anyway.
Presumably, once we have fast stepping and the size of the register,
and the key, we can just step 2**n - 1 positions back to plaintext.
>> Now, I've never tried to recover LFSR
>> step distance knowing initial and resulting values, and with multiple
>> registers that sounds tough.
>
>Here's an observation: if you know the entire contents of the register
>before and after the stepping, and you know the taps, then recovering
>the step distance (for a n-bit LFSR) is just a discrete log problem over
>GF(2^n).
This may take your breath away, but I have myself never solved a
discrete log problem.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
