Cryptography-Digest Digest #664, Volume #12 Tue, 12 Sep 00 18:13:01 EDT
Contents:
Re: sac fullfilling decorelated functions (Tom St Denis)
Re: nice simple function (Tom St Denis)
Re: Steganography and secret sorting ("Douglas A. Gwyn")
Re: Need Tiger hash results for sample test data ([EMAIL PROTECTED])
Re: nice simple function (Tom St Denis)
Re: Intel's 1.13 MHZ chip ([EMAIL PROTECTED])
Re: Steganography and secret sorting (Matthew Skala)
Re: Weaknesses in this algorithm? (ArchimeDES)
search for better serpent sboxes (Tom St Denis)
Re: nice simple function (Simon Johnson)
Re: search for better serpent sboxes (Simon Johnson)
Re: Problem with Tiger hash algorithm and binary files (Konrad Podloucky)
Re: Known Plain Text Attack (Terry Ritter)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: sac fullfilling decorelated functions
Date: Tue, 12 Sep 2000 20:07:13 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> >
> > Let's take F(x) = a.x + b in GF(2)^32, now we want to know for any
> > multiple of 'a' in the same field what is the prob of at laest 16
bits
> > being set... so I take out some new finite I learnt and plug in (32
> > choose 16)/2^32 = 2^-2.837. This means about 1 in 6 will be SAC
> > fullfilling functions.
> >
> > Over the entire multiplcation we find 32/6 ~ 5.3 which means of the
32
> > multiples of 'a' only 5 are sac fullfilling. If 'a' is random there
> > distribution should be random (?). Now consider the lower bits,
such
> > as with only four bits set. We find them with a prob of 2^-16.865
much
> > less then with 16 bits.
> >
> > In any GF multiply the chances of any being of only four bits is
about
> > 2^-11 or 1 in 2048. This means that GF multiplication is a closely-
sac-
> > like function most of the time, and for a fraction of the time not.
> >
> > Can this be used to extract information from the function in those
> > specific cases (extreme cases?)
>
> F is linear. That's a much bigger problem :-)
Actually in Vaudenays paper if 'a,b' is random the function is immune
to linear cryptanalysis.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: nice simple function
Date: Tue, 12 Sep 2000 20:09:03 GMT
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
> Tom St Denis wrote:
> > f''(x) = f'(x ++ f(x)) where '++' represents modular integer
addition.
> > We now get f''(x) = f'(x ++ (a.x + b)) = c.(x ++ (a.x + b)) + d =
c.x
> > ++ c.(a.x + b) + d = c.x ++ (c.a.x + c.b) + d
> >
> > From what I can tell c.x cannot be grouped with c.a.x, which means
we
> > have an output that is a function of 'c' and 'a'. Also that c.b
cannot
> > be grouped with 'd', but since they are not a function of the input
can
> > we let 'b' be zero and just have f''(x) = (c.x ++ c.a.x) + d
> >
> > Which leads me to f''(x) = (a.x ++ b.x) + c as a new decorrelated
> > function. (Assuming a, b != 0).
> >
> > Am I nuts or what? Please comment :-)
>
> Plot it and see. Try 4 bits, so you have 4*4*4*4 possible pairs ( a
nice
> round number!) for each of a, b, c and x. What is the distribution of
> f''(x) as a function of a, c and x. I'm assuming the modulus is 2^4
as
> well, but you could really have fun by changing that :-)
The modulus is a degree 5 primitive polynomial in GF(2), or just the
integer 17 and use 1-16 as elements.
I will play around with it.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Steganography and secret sorting
Date: Tue, 12 Sep 2000 19:40:53 GMT
Mok-Kong Shen wrote:
> Sorry, I am not yet able to understand. Could you explain
> with a database of, say, 5 or 10 entries? Do you assume
> that the same database (without permutation) is available
> to both partners? Thanks.
The hard part is encoding the hidden message in terms of
a permutation. Supposing that to have been done, so the
permuted order for the coded message is 4,1,5,3,2 then
he transmitted database might be
Texas
Alaska
Vermont
Ohio
Wyoming
which when sorted (on the final letter in this example) is
Alaska
Wyoming
Ohio
Texas
Vermont
The reordering from the sorted database to the transmitted
one is readily found to be 4,1,5,3,2 which recovers the
coded message. Then whatever coding was applied is
inverted to get the intended message.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Need Tiger hash results for sample test data
Date: Tue, 12 Sep 2000 20:47:46 GMT
In article <[EMAIL PROTECTED]>,
John Myre <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
> <snip>
> > A hash
> > on a string SHOULD not be the same as hash on a file containing said
> > string
> <snip>
>
> Huh? Why not?
>
> JM
>
Well, for starters, lets consider an example with our old friend md5. If
I want to create an md5 hash on the string 'abc', I could simply run:
'md5 -sabc', which yields:MD5 ("abc") = 900150983cd24fb0d6963f7d28e17f72
This is not, however, what I would get if I created a file (abc.txt),
containing the string 'abc' and then ran md5 against it as: 'md5
abc.txt' or 'cat abc.txt | md5'. Both of these would yield:
MD5 (abc) = 0bee89b07a248e27c83fc3d5951213c1
I could also run: 'echo abc | md5', but my default echo (shell built-in)
adds a newline to the end of the string which yields:
0bee89b07a248e27c83fc3d5951213c1
Clearly, I have to get the newline out by using something like this:
'/usr/ucb/echo -n abc | md5'. This will produce:
900150983cd24fb0d6963f7d28e17f72
I have tested this scenario on RIPEMD-160, SHA (actually SHA1), and
several others and the behavior is consistent. In the case of Tiger, I
found that if I wrote a C routine that hashes standard input using their
routine, I did not get the same hash for 'abc'. However, if I ran
something like: '/usr/ucb/echo -n abc | routine', then it matches.
I would like to get some sample hashes for actual files to be certain my
routine is correct. Particularly in in the area of binary files since
things get a little weird there.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: nice simple function
Date: Tue, 12 Sep 2000 20:59:42 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Bryan Olson wrote:
> > Tom St Denis wrote:
> > > My goal is to change the function so even knowledge of two
> > > pairs is not > sufficient, but somehow I have the feeling
> > > my other idea f(x) = (a.x ++ > b.x) + c, won't work well
> > > either... I have to think it over
> > Well, there is:
> > f(x) = a_2.x^2 + a_1.x + a_0
> > How many pairs of (x, f(x)) would it take to determine
> > (a_0, a_1, a_2) ?
>
> Typically three, since when one plugs in known values a
> linear relationship among the parameters results. With
> the function Tom suggested, the > operator loses so much
> information (inputs two numbers and outputs a single bit)
> that it would take a fair amount of searching to nail down
> the parameters. Of course, the down side of using such a
> function is that the attacker can be rather inaccurate in
> his guesses for the key parameters and still be able to
> read the message, in some instances.
True, the goal is to use f''(x) in some round function as a function to
be immune to order 2 attacks.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Intel's 1.13 MHZ chip
Date: 12 Sep 2000 21:30:51 GMT
John Savard <[EMAIL PROTECTED]> wrote:
> The original 8088 was 4.77 MHz, but there were 1 MHz versions of the
> 8080 and 6800, if I'm not mistaken.
Actually, it's been a long time, but I seem to remember that the 8080
ran at up to 2 MHz, and the 8080A upped that to 4MHz....
--
Steve Tate --- srt[At]cs.unt.edu | Gratuitously stolen quote:
Dept. of Computer Sciences | "The box said 'Requires Windows 95, NT,
University of North Texas | or better,' so I installed Linux."
Denton, TX 76201 |
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Steganography and secret sorting
Date: 12 Sep 2000 14:27:01 -0700
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Sorry, I am not yet able to understand. Could you explain
>with a database of, say, 5 or 10 entries? Do you assume
>that the same database (without permutation) is available
>to both partners? Thanks.
It's available to both partners because it is transmitted. Let's say my
very special secret message for you is "3 1 4 1 5". I send you a message
something like this:
Dear Mok-Kong Shen:
Here is the suggested guest list for the dinner party, in no particular
order: Christina, Alice, Fred, Bob, Isobel, David, Ellen, Griselda,
Herbert.
- Matthew Skala
When you recieve the message, you put the names in alphabetical order:
Alice
Bob
Christina
David
Ellen
Fred
Griselda
Herbert
Isobel
Then you number them, and look up the first name I listed (Christina).
It's number 3. (A computer implementation would most likely count
starting at zero, but for this demo I'm using 1-based numbering.) So the
first integer in the message is "3". Then you remove Christina from the
list, and look up the next name, Alice. Alice is number 1. Then you
remove that name from the list and look up Fred, which will be 4. After
removing Fred, Bob is number 1 on the remaining list, and with Bob
removed, Isobel is number 5. So you've recovered the secret message "3 1
4 1 5" from my apparently-innocuous list of names.
A real implementation would have to be a little more sophisticated; for
one thing, as the list gets shorter you are able to transmit less and less
information with each name. Also, it would be safest not to use pure
alphabetical order for the list of names. We agree in advance on some
method of ordering the names. Note that that doesn't mean we have to
transmit the database in advance, only some way of ordering it (which
constitutes the key). For instance, we could agree (as another poster on
this thread suggested) to sort according to the last character first. We
have to express the message as a permutation on the database. As I
suggested elsewhere on this thread, arithmetic coding can provide a
frugal way of doing that part.
The essentials of this scheme are:
* We transmit a database which may plausibly be transmitted in any
order; we pretend that the order of transmission has no significance
* We have agreed on a way of ordering it
* The secret message is mapped into a permutation on the database
* Transmitter orders the database in the agreed way, and then permutes it
according to the message
* Receiver orders the database in the agreed way, and uses that to
determine what permutation the transmitter applied
* The permutation is mapped back into a message
--
Matthew Skala
[EMAIL PROTECTED] I'm recording the boycott industry!
http://www.islandnet.com/~mskala/
------------------------------
From: ArchimeDES <[EMAIL PROTECTED]>
Subject: Re: Weaknesses in this algorithm?
Date: Tue, 12 Sep 2000 21:50:03 GMT
On 11 Sep 2000 16:32:11 GMT, [EMAIL PROTECTED] (Mark Wooding) wrote:
>Patrick Schultz <[EMAIL PROTECTED]> wrote:
>> encrypting:
>> 1) xor the plaintext with a one-time pad
>> 2) encrypt the one-time pad with rc4 using a random key that is the same
>> length as the passphrase.
>> 3) xor the passphrase with the random key.
>
>So, we have a message M, a passphrase P, a random RC4 key K, and a
>one-time pad R. We send
>
> P \xor K, R \xor RC4(K), M \xor R
Hmmm, no:
we send P \xor K, RC4(K,R), M \xor R.
However with this system we lose the total security of OTP, an
attacker has only to break RC4.
=======================
remove DIESPAM from address for mail
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: search for better serpent sboxes
Date: Tue, 12 Sep 2000 21:42:23 GMT
With my sboxgen program [1] I am searching for 4x4 sboxes that have a
LPmax of 4, a DPmax of 4, fulfill SAC and BIC (order 3).
Currently on my comp I get about 250,000 sboxes tested per second, but
if we had 1000 comps searching that would be an awesome figure. On my
website
[1] www.geocities.com/tomstdenis/
I have a copy of sboxgen in source form, but I modified it at home to
also give a rate output display while it's searching. If anyone want's
an executable form of the program I am more then happy to share it.
I could even embed the parameters so no setup is required!
These sboxes could be used in serpent as replacement functions...
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: nice simple function
Date: Tue, 12 Sep 2000 21:45:40 GMT
Right, what is linearness? - Clearly its a measure of the vunrability
to attack by linear cryptanaylsis. So the next question is what is
linear cryptanylsis? I don't think this question has ever been answered
properly while i've been posting/reading. :)
Thanxs :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: search for better serpent sboxes
Date: Tue, 12 Sep 2000 21:52:19 GMT
In article <8pm7vp$ibl$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> With my sboxgen program [1] I am searching for 4x4 sboxes that have a
> LPmax of 4, a DPmax of 4, fulfill SAC and BIC (order 3).
>
> Currently on my comp I get about 250,000 sboxes tested per second, but
> if we had 1000 comps searching that would be an awesome figure. On my
> website
>
> [1] www.geocities.com/tomstdenis/
>
> I have a copy of sboxgen in source form, but I modified it at home to
> also give a rate output display while it's searching. If anyone
want's
> an executable form of the program I am more then happy to share it.
>
> I could even embed the parameters so no setup is required!
>
> These sboxes could be used in serpent as replacement functions...
>
> Tom
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Ask distributed.net and see if they'll let you code a thingy for this
task! If not, clone it :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Konrad Podloucky <[EMAIL PROTECTED]>
Subject: Re: Problem with Tiger hash algorithm and binary files
Date: Wed, 13 Sep 2000 00:00:10 +0100
In article
<[EMAIL PROTECTED]>, Daniel
Leonard <[EMAIL PROTECTED]> wrote:
> On Tue, 12 Sep 2000, John Myre wrote:
>
>> Daniel Leonard wrote:
>> <snip>
>> > While on the subject, which reference implementation is the right
>> > one: =
> the
>> > one from Eli Biham site, or the one from Ross Anderson site ?
>>=20
>> How are they different? Do they give different answers?
>
> Last time I checked (around April-May), the difference in the
> implemetation was in the padding.
>
> Anderson's: 0x80, 0x00, ...
>
> Biham's : 0x01, 0x00, ...
>
> It gives different results. In the paper, the padding is stated as
> follow:
>
> the bit 1 followed by as many 0 bit as necessary to pad
>
> (not verbatim, but close enough IIRC).
>
> I had an acknowledgement with Mr. Anderson, but no answer since then
> about this difference neither which is the coorect one (I favor
> Anderson's since it was how I interpreted the paper).
>
>From Eli Biham's Tiger page
(http://www.cs.technion.ac.il/~biham/Reports/Tiger/):
"[...]Note that in the original reference implementation that we have
published in this page there was a typo that used the wrong bit
order when it padded the '1' bit at the end of the message. It
used the constant 0x80, rather than 0x01 to append this bit. The
reference implementation and test results given above are already
corrected. We are grateful to John Lull who found this typo."
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Known Plain Text Attack
Date: Tue, 12 Sep 2000 22:00:52 GMT
On 12 Sep 2000 17:22:17 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>
>> First of all, my US patents apply only in the US,
>
>Clearly. Do you hold patents in other countries, though?
No. Sorry.
>> Next, if the issue is *understanding* cryptographic techniques,
>> avoiding patented concepts is an explicit choice for ignorance.
>
>Agreed.
>
>Terry's put together a great deal of really useful information. He also
>explains clearly which techniques he's patented, which lets you avoid
>them. His site is well worth a look.
Patents support the business of research. If someone imagines that
academic research is all we need, I guess they must support the
limitations on crypto possibilities that academia enforces. They also
ignore the fact that RSA itself was academic research. Most people
here seem to support exactly the process which caused the most
problems in the first place.
Somebody has to pay for work, or that work cannot continue. If one
could just walk out of a store without paying for a can of beans,
there soon would be no beans, or no store, which is exactly what NSA
wants. Now, maybe academics really will produce all the beans we
need, if we just learn to like the beans they make. But a real
industry is driven by customer feedback in terms of cash, and reacts
to produce what the customer really wants and needs at an acceptable
price. That doesn't sound like the academia I know.
Cryptography is not about sharing; we can call it privacy, but
whatever we call it, the basis of cryptography is the exact opposite
of free sharing with everyone. Cryptography is about keeping from
others; cryptography is conflict; cryptography is war. And AES is not
about making cryptography free for users; it is instead a way to give
manufacturers a component without which they would have had to support
independent cryptographic research.
I describe my stuff as clearly as I can because I am happy to have it
compared to other work. I think the majority of my pages are not what
I have done, but instead what one might want to know. I don't cover
everything, but I do cover a lot, and it is free to users (I pay the
web host costs), so you don't have to buy a book or even check one out
to read it. Since when is it more respectable to sell information
that people need, then to extract a license fee from the sale of
something being sold at a profit?
What is really embarrassing to me about all this is the lack of
academic research which would place my work in a proper context. That
lack is nothing less than an inherent and appalling criticism of
academia itself. The lack of action reveals what academic goals
really are, as opposed to what society might like them to be.
As a society, our goal should be to get the best cryptography we can
get, at a fair price, instead of simply taking whatever academics want
to give us for free, with whatever analysis they wish to contribute,
also free. Our goal ought to be to have a competitive industry of
cryptography which can support its own research out of profits. But
that would mean somebody actually would have to pay for a cipher.
The idea that AES will give us all the cipher we need for free is
fatally flawed in many ways. Having just come through DES weakness,
one might think that everyone would already know that we need to be
able to change ciphers quickly, without re-building our entire
security system. We need systems which allow ciphers to be quickly
changed, as well as a variety of alternative ciphers to snap in, and
the ability to identify and use different ciphers. And since we
cannot measure the strength of our ciphers, if we really are concerned
about security, we need to use multi-ciphering. I suppose it is only
to be expected that there would be oh-so-much concern about patents,
and relatively little concern about the real issues before us.
Presumably our opponents appreciate the irony.
---
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
******************************
