Cryptography-Digest Digest #793, Volume #11 Tue, 16 May 00 22:13:00 EDT
Contents:
Re: Creating a good key-shedule (Tom St Denis)
Re: Is OTP unbreakable? (Mickey McInnis)
Re: Permutation Polynomials (Polly & Jim Steuert)
Re: About Hardware RNG (Will Dickson)
Re: Permutation Polynomials (Tom St Denis)
Re: Tiny Stream Cipher "slime" (Tom St Denis)
Re: About Hardware RNG (Tom St Denis)
Re: Is OTP unbreakable? (Tim Tyler)
Re: Unbreakable encryption. (Tim Tyler)
Q: How to find good characteristics for differential cryptanalysis? (JBR)
Re: Interleaving for block encryption (Tim Tyler)
Fixed the stream cipher "Slime"? (Tom St Denis)
Re: Definition of "Broken" Cipher (Nicol So)
Re: Theoretical question (Bryan Olson)
Re: Fixed the stream cipher "Slime"? (Tom St Denis)
Re: Theoretical question (Bryan Olson)
Re: Tiny Stream Cipher "slime" (Gregory G Rose)
Re: Prime Generation in C,C++ or Java (Bryan Olson)
Re: AES final comment deadline is May 15 (Bryan Olson)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Creating a good key-shedule
Date: Tue, 16 May 2000 23:01:09 GMT
In article <8fsgvf$76l$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Fair enough, 32-bit enough or would u use a large bits size?
I would say at the very least 48 bits... but I would stick with 64 bits
as a min, since it's kinda standard.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Mickey McInnis)
Subject: Re: Is OTP unbreakable?
Date: 16 May 2000 23:11:40 GMT
Reply-To: [EMAIL PROTECTED]
In article <8fr420$j1o$[EMAIL PROTECTED]>, Simon Johnson <[EMAIL PROTECTED]>
writes:
|> ...
|>
|> Encrypting with a OTP is pointless simply because
|> now you now have to figure out a way to secure the OTP key!!!!!!!
|> ....
The usual way is to send a large pad ahead of time by some more secure,
but non-real-time channel, such as a courier, or giving it to your
correspondent in person before he travels through "enemy" territory. A
single CD-R disk would contain enough pad for 100,000 single spaced
standard typewritten pages.
It's not always practical, but for many situations, it can be.
--
Mickey McInnis - [EMAIL PROTECTED]
--
All opinions expressed are my own opinions, not my company's opinions.
------------------------------
From: Polly & Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: Permutation Polynomials
Date: Tue, 16 May 2000 19:46:01 -0400
I did a fair amount of web searching and did not
find any references at all to algorithms for inverses of
permutation polynomials save what was posted in
threads here two weeks ago. So I thought this might
be a contribution. Please let me know if you have any
references to such algorithms.
Being new to sci.crypt, I was not aware of that protocol, and I
have no web site to place a 550-line c program. But I've been warned now.
-Jim Steuert
Tim Tyler wrote:
> Dann Corbit <[EMAIL PROTECTED]> wrote:
>
> : Some prototypes are missing unless you add stdlib.h
>
> The whole thing should have been missing.
>
> Posting binary files to multiple different threads on sci.crypt is
> not a good idea.
>
> In the future, could such authors please use a web site - and post a
> pointer - instead.
> --
> __________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
> |im |yler The Mandala Centre http://mandala.co.uk/ UART what UEAT.
------------------------------
From: [EMAIL PROTECTED] (Will Dickson)
Subject: Re: About Hardware RNG
Date: Wed, 17 May 2000 00:05:36 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
>I was wondering (being spoiled as I am) does anyone have a bread-boarded
>version of
>
>http://world.std.com/~wware/hw-rng.html
>
>Using either a 18v input or on-board 9v batt supply?
>
>That you can spare? I want to try it out, but I don't know how to read
>the diagram properly (I know the basic symbols....).
Which bit of the diagram are you having trouble with? (This is a tad
OT so email me if you'd prefer).
FWIW I built a circuit a little while ago that worked on the same
principle (i.e. sampling noise from a reverse-biased zener).
Some typical results, from a 1024-byte sample (taken one bit at a
time):
Entropy 7.647 bits / byte
chi-sq probability 0.01%
mean 148.17
serial correlation 0.0173
In short, it's strongly biased, and hence not really random on its
own; I suspect this is where the lousy chi-square comes from. However,
there does appear to be good entropy there, so provided it's fed into
a cryptosecure hash you should get good results (is MD2 up to the
job?). I'm planning to assume 4 bits per byte of real entropy to allow
for the limited predictability the circuit gives.
A couple of implementation issues to bear in mind:
1. If your +ve rail has significant ripple then this is coupled into
the noise generator and turns it into a 50Hz oscillator (assuming 50Hz
ripple). 9V battery should be OK, mains-powered "battery eliminator"
will need to go through a good regulator first. Since the circuit
state will be osciallating rapidly, your battery life may be much
shorter than you might think.
2. put a small capacitor as close as you can get to the power-supply
pins of the logic chip. ALS may be more forgiving, but certainly AC
logic tends to dump charge pulses onto its rails when it switches.
Regards
Will.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Permutation Polynomials
Date: Wed, 17 May 2000 00:21:49 GMT
In article <[EMAIL PROTECTED]>,
Polly & Jim Steuert <[EMAIL PROTECTED]> wrote:
>
> I did a fair amount of web searching and did not
> find any references at all to algorithms for inverses of
> permutation polynomials save what was posted in
> threads here two weeks ago. So I thought this might
> be a contribution. Please let me know if you have any
> references to such algorithms.
>
> Being new to sci.crypt, I was not aware of that protocol, and I
> have no web site to place a 550-line c program. But I've been warned
now.
Email your papers/source/misc and I can host them in
http://www.tomstdenis.com/sci.crypt/
Tom,
[EMAIL PROTECTED]
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Tiny Stream Cipher "slime"
Date: Wed, 17 May 2000 00:34:44 GMT
In article <8fsg5a$611$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> Hello,
>
> I just designed a compact, simple and somewhat fast stream cipher
which
> I called (for some reason) Slime. It requires all of 16 bytes of ram
> to work, and can be written in under 50 or so lines of code (most of
> which is the sbox).
>
> My mini-paper at (http://www.tomstdenis.com/slime.txt) includes source
> and test vectors.
>
> I have tried to poke at it a bit, I dunno if it's really secure, but
it
> looks nice.
>
> Any feedback would be nice.
>
> Thanks,
> Tom
Wow, I just noticed something.... I make up two keys K1 and K2, I make
K2 differ by one bit. Then I xor the two streams together... expecting
the output to pass diehard... it fails misserably...
Any ideas to why it fails?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: About Hardware RNG
Date: Wed, 17 May 2000 00:43:20 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Will Dickson) wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> >I was wondering (being spoiled as I am) does anyone have a bread-
boarded
> >version of
> >
> >http://world.std.com/~wware/hw-rng.html
> >
> >Using either a 18v input or on-board 9v batt supply?
> >
> >That you can spare? I want to try it out, but I don't know how to
read
> >the diagram properly (I know the basic symbols....).
>
> Which bit of the diagram are you having trouble with? (This is a tad
> OT so email me if you'd prefer).
>
> FWIW I built a circuit a little while ago that worked on the same
> principle (i.e. sampling noise from a reverse-biased zener).
>
> Some typical results, from a 1024-byte sample (taken one bit at a
> time):
>
> Entropy 7.647 bits / byte
> chi-sq probability 0.01%
> mean 148.17
> serial correlation 0.0173
>
> In short, it's strongly biased, and hence not really random on its
> own; I suspect this is where the lousy chi-square comes from. However,
> there does appear to be good entropy there, so provided it's fed into
> a cryptosecure hash you should get good results (is MD2 up to the
> job?). I'm planning to assume 4 bits per byte of real entropy to allow
> for the limited predictability the circuit gives.
I plan to do the same thing. Buffer up some input, hash and output the
digest.
> A couple of implementation issues to bear in mind:
>
> 1. If your +ve rail has significant ripple then this is coupled into
> the noise generator and turns it into a 50Hz oscillator (assuming 50Hz
> ripple). 9V battery should be OK, mains-powered "battery eliminator"
> will need to go through a good regulator first. Since the circuit
> state will be osciallating rapidly, your battery life may be much
> shorter than you might think.
Well I have to figure out a power supply for the device. I think I may
have a power supply (i.e batteries) for the mcu, but steal power from
the rs-232 port for the rng. Since my friend showed me how to tie +10/-
10 to get a +20v power (which is simple thing for you guys, but all new
for me).
> 2. put a small capacitor as close as you can get to the power-supply
> pins of the logic chip. ALS may be more forgiving, but certainly AC
> logic tends to dump charge pulses onto its rails when it switches.
This design has a power supply right after the transistor (or diode)
and ones right before each inverter step. Although I may consider this
with him as well.
> Regards
>
> Will.
Thanks for the info.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Is OTP unbreakable?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 16 May 2000 23:56:49 GMT
Simon Johnson <[EMAIL PROTECTED]> wrote:
: Encrypting with a OTP is pointless simply because now you now have
: to figure out a way to secure the OTP key [...]
The significant difference being that the OTP can be secured well in
advance of sending the communication - at a time when you did not know
what message was eventually going to be transmitted.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Unbreakable encryption.
Reply-To: [EMAIL PROTECTED]
Date: Wed, 17 May 2000 00:01:59 GMT
[EMAIL PROTECTED] wrote:
: I mean this thing would be so powerful even NSA can't
It looks like they could - and did: cutting him off in mid-sentence no less ;-)
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: JBR <[EMAIL PROTECTED]>
Subject: Q: How to find good characteristics for differential cryptanalysis?
Date: Tue, 16 May 2000 20:56:25 -0400
[This is a re-post]
Hello sci.crypt'ers,
Given an iterated cipher, how would you go about finding
high-probability characteristics for differential cryptanalysis?
I've read several descriptions of differential cryptanalysis and
understood them (for the most part, but not completely). What the
authors didn't say was how they came up with the high-probability
characteristics in the first place.
Is there a surefire method for finding the most probable n-round
characteristic for specific round structures?
If not, what would be a good heuristic for finding good (but not
necessarily optimal) n-round characteristics for unfamiliar round
structures?
In general, are the characteristics used in published differential
cryptanalyses known to be optimal, or do they just work well enough?
I don't have convenient access to a technical library, so a brief
description of the relevant algorithms and heuristics would be helpful.
(Pointers are welcome too, of course).
My sincere thanks in advance.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Interleaving for block encryption
Reply-To: [EMAIL PROTECTED]
Date: Wed, 17 May 2000 00:33:57 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Mok-Kong Shen wrote:
:> It is my intuitive belief that using a weak cipher, e.g. a simple
:> transposition, to pre-process the plaintext before feeding it to
:> a good block cipher ( i.e. one has now a superencryption) essentially
:> contritutes to defeating the opponent's brute forcing [...]
: [...] Historically, systems have combined two forms of encryption
: such as codebook+polyalphabetic_substitution, and cryptanalysts
: have found ways to more or less routinely strip off one of the
: layers of encryption so that they could work on the other. [...]
That's true in some cases - and not in others. In some cases, stripping
of one layer was possible due to obtaining its keys from other traffic.
This was a weakness of a particular implementation, not really anything to
do with the idea of using multiple encyphering itself.
: In the context of modern block ciphers, any extra key bits
: would be better used in a single integrated encipherment than
: split between two orthogonal encipherments.
This issue has come up here before.
The argument for using separate cyphers is not that it is theoretically
stronger than a unified algorithm with a longer key. The reverse is the
case - it you want strength you dividing your cypher into separable
components applied in series is almost certainly a bad idea.
The argument is more along the lines that making a large cypher with a
longer key properly secure is not a process that is properly understood.
You can't just feed more entropy into the round keys of a symmetric
algorithm and expect its security to increase in proportion. Nor is there
necessarily an easy way to bump up the block size. Scalable block
cyphers exist; but the extent to which their security properties scale
is likely to remain questionable.
Applying cyphers in series can be done using existing, well-understood
components. There are some definite advantages to applying multiple
layers of encypherment - when compared to using a single larger cypher.
There is also the (severe) disadvantage you mention, of orthogonality.
There /are/ some things that can be done to prevent attacks that treat the
resulting construct like an onion - and peel off its layers.
To name one, it would often be possible to encrypt each block with one
cypher, and then encrypt it with the other one, /before/ applying a
chaining mode to the results.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Goodbye cool world.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Fixed the stream cipher "Slime"?
Date: Wed, 17 May 2000 01:06:20 GMT
I found if I changed the constant '1' to something with 16 significant
bytes (the simplest constant I could find see the paper) I get way
better results.
The revised paper is at
http://www.tomstdenis.com/slime.txt
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Definition of "Broken" Cipher
Date: Tue, 16 May 2000 21:20:58 -0400
Reply-To: see.signature
Paul Koning wrote:
>
> 2^20 blocks is NOT a long time! That's only 64 (or 128 for AES)
> megabits. That's less than a second of traffic for the sort of
> high speed links you can get as a high end Internet *user*, never
> mind the far faster links used in the Internet core. (The latter
> are less relevant since encryption is normally an end to end
> activity. But if you have an OC-3 link into the Internet, you're
> not particularly likely to rekey as often as you suggest, not
> by a long shot.
I'm not so sure about the "not by a long shot" part. Rekeying at this
rate is very doable.
> Indeed, one of the arguments against *all* 64-bit blocksize ciphers
> is that you need to rekey within 2^32 blocks, and that's rather fast
> for modern high speed traffic...
Again, I don't think the rekeying requirement is too harsh. Consider an
OC-48 link, which has a bit rate of 2.488Gbps. It would take about 110
seconds to transmit 2^32 64-bit blocks. Rekeying at this frequency (or
one or two orders of magnitude higher) is very feasible.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Theoretical question
Date: Wed, 17 May 2000 01:23:54 GMT
[EMAIL PROTECTED] wrote:
>
> I have a kind of math-theoretical question about probability
[...]
> 1. Is my theoretical computation correct,
Yes, I get the same thing. To state is so that people don't
need to follow all the notation:
Suppose we have many pigeons and many pigeon-holes and the
holes/pigeons ratio is r. If each pigeon independently
picks a random hole to fly into, then the ratio of occupied
holes to all holes should be close to:
1 - e^-r
(I'll include Raenye's derivation below. It's quite neat if
one takes the time to follow.)
> and if so,
> 2. Does the C program attached I used to compute iterations lose
> accuracy quickly,
I think the numbers are reasonable, but I'm not sure how
to check.
>and if not so,
> 3. Why does it take so much iterartions to get m_N feasible
> (e.g., to get m_N = sqrt(m_0), more than 2^30 iterations are
> required!
> problem circumstances point out N should be ~ 2^10)
Obviously as i increases, r_i decreases, but quickly
flattens out. I think a cryptographer would regard the
large number of iterations required as good news.
One of the results of your math is that the ratio r_i is
about the same for all "large" starting values. I don't see
what sqrt(m_0) has to do with it. To collapse a set of size
2^80 to an image of size 2^40 takes about the same number of
iterations as to collapse 2^160 to 2^120.
Can you state the problem circumstances that lead you to the
2^10 figure? The first suspicion to follow is that model is
not really fulfilled.
--Bryan
> Definitions
> ===========
>
> M_0 is a (large) set, say {0, 1} ^ 80
> f_i : M_0 -> M_0; i = 0, 2, ..., N-1
> M_(i+1) = f_i[M_i)] = { f_i(a) : a <- M_i }; i = 1, 2, .., N-1
> m_i = E(| M_i |)
>
> That is, we map M_0 into a subset M_1 of M_0 using f_0,
> then map M_1 into a subset M_2 of M_0 using f_1 and so on.
>
> f_i are random functions.
>
> I want to find m_N.
>
> Step I
> ======
>
> Pr(x <- M_(i+1)) = 1 - ((1 - 1/m_0)^m_i)
> (not choosing x as the image of any y <- M_i)
>
> Step II
> =======
>
> m_(i+1) = m_0 * E(Indicator_{x <- M_(i+1)}) = m_0 * Pr(x <- M_(i+1)) =
> = m_0 - m_0 * (1 - 1/m_0)^m_i)
> (linearity of expectancy)
>
> Step III
> ========
>
> Let r_i = m_i / m_0.
> Divide the equation from II by m_0 to get the system
>
> r_0 = m_0 / m_0 = 1
> r_(i+1) = 1 - (1 - (1/m_0)) ^ (m_0 * r_i) ~= 1 - e^(- r_i)
> (as m_0 is very large)
>
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Fixed the stream cipher "Slime"?
Date: Wed, 17 May 2000 01:26:32 GMT
In article <8fsra4$ibl$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> I found if I changed the constant '1' to something with 16 significant
> bytes (the simplest constant I could find see the paper) I get way
> better results.
>
> The revised paper is at
> http://www.tomstdenis.com/slime.txt
>
> Tom
And of course my test vectors don't match for DJGPP and Turbo C... sure
why not... it's all byte arithmetic... arrrrrggggg!!!!!!..
Any help....?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Theoretical question
Date: Wed, 17 May 2000 01:30:31 GMT
Mok-Kong Shen wrote:
>
>
> Nicol So wrote:
>
> > A "random function" is usually taken to mean a function
> > chosen uniformly at random from the set of all functions
> > with a given domain and codomain. That's probably what
> > the original poster meant.
>
> Under that very general assumption (all functions without
> restrictions to the properties) I don't yet see that much
> useful properties could be derived therefrom.
But the parenthesized description is not at all the same as
the definition Nicol So stated. A random function is not
all functions nor an arbitrary choice. It's a random
choice, with all candidates equally probable.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: Tiny Stream Cipher "slime"
Date: 16 May 2000 18:44:26 -0700
In article <8fspf4$gd3$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>Wow, I just noticed something.... I make up two keys K1 and K2, I make
>K2 differ by one bit. Then I xor the two streams together... expecting
>the output to pass diehard... it fails misserably...
The main loop always permutes the possible values,
with respect to the key bytes. Therefore, when the
key bytes differ, the outputs *must* differ, so
the XOR of them *must* be non-zero. You bias
against accidental collisions.
regards,
Greg.
--
Greg Rose INTERNET: [EMAIL PROTECTED]
QUALCOMM Australia VOICE: +61-2-9181 4851 FAX: +61-2-9181 5470
Suite 410, Birkenhead Point http://people.qualcomm.com/ggr/
Drummoyne NSW 2047 B5 DF 66 95 89 68 1F C8 EF 29 FA 27 F2 2A 94 8F
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Prime Generation in C,C++ or Java
Date: Wed, 17 May 2000 01:39:19 GMT
Wei Dai wrote:
> [EMAIL PROTECTED] says...
> > I disagree. The exposed functions, even if implemented
> > efficiently, are not useful in building efficient generators
> > for primes of important special forms, for example DSA
> > primes. To find DSA primes I want to simultaneously sieve
> > for candidate pairs (q, p=d*q+1) where neither has a small
> > factor, then do exactly one iteration of Miller-Rabin (with
> > base 2) on q, then if that passes do the same on p, then if
> > that passes do several randomized iterations to certify
> > both. I have to write my own sieve and Miller-Rabin test
> > because the class doesn't expose the ones it already has.
>
> With DSA, is there any advantage to simultaneously sieving
> for p and q, instead of the traditional method of generating
> q first and then generating prime p of the form d*q+1? (Of
> course the traditional method is not supported by the Java
> BigInteger interface either.)
Oops, no. I was thinking of generating primes for
encryption (or both signing and encryption) where I'd want
d/2 prime.
>
> What is your ideal interface for prime number generation?
> Would you care to comment on the interface in Crypto++:
I like interfaces that I can use at a variety of levels.
I'll look at the Crypto++ prime generation calls when I get
a chance, but for now I'll say that in general I think
Crypto++ is the class act in open crypto libraries.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: AES final comment deadline is May 15
Date: Wed, 17 May 2000 01:48:45 GMT
David A Molnar wrote:
> Bryan Olson wrote:
>
> > cipher. But sci.crypt's obsession with secret key encryption
> > is out of touch with both modern cryptology and the
> > cryptographic market. AES is not among the "New Directions
> > in Cryptography". It's a replacement for DES.
>
> Out of curiosity, what do you think is more in touch with modern
> cryptology and the cryptographic market?
Of course "New Directions" is an allusion to the Diffie-Hellman
paper of 1976.
I think the market is in using cryptography to build security
into the systems that people already use, without making them
much harder to use.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
