Cryptography-Digest Digest #893, Volume #10 Wed, 12 Jan 00 22:13:01 EST
Contents:
Re: Intel 82802 Random Number Generator (Michael Sierchio)
Re: AES & satellite example ("Roger Schlafly")
Re: lfsr - polynom (Gregory G Rose)
Re: Blum, Blum, Shub generator (Michael Sierchio)
Re: Square root attacks against DSA? (David Hopwood)
Re: Questions about message digest functions ([EMAIL PROTECTED])
Re: "1:1 adaptive huffman compression" doesn't work (Tim Tyler)
Re: Blum, Blum, Shub generator (Thierry Moreau)
Re: Blum, Blum, Shub generator (Tim Tyler)
----------------------------------------------------------------------------
From: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: Intel 82802 Random Number Generator
Date: Wed, 12 Jan 2000 17:21:40 -0800
John Savard wrote:
> It's interesting that Intel was able to get a patent on implementing
[von Neumann technique geschnipped]
> in hardware, despite the fact that the technique, in software, is as
> old as the hills.
I doubt that it's as simple as that -- we'll have to wait and read
the patent when it's issued.
--
QUI ME AMET, CANEM MEUM ETIAM AMET
------------------------------
From: "Roger Schlafly" <[EMAIL PROTECTED]>
Subject: Re: AES & satellite example
Date: Wed, 12 Jan 2000 16:38:54 -0800
Jerry Coffin <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> This is not a point I missed. In fact, it's one I addressed directly.
> You'd want to do this if you had reason to believe that all the
> ciphers you could include at launch time were at least somewhat likely
> to be broken. I'm convinced that this possibility is so remote that
> there's nothing to be gained by trying to design against it.
So you are claiming that today's technology is such that we can
design 5 ciphers and be certain that at least one of them is secure,
but we cannot design one cipher and be certain it is secure?
You might be right, but it seems like a peculiar position to me.
25 years ago, if the US had adopted 5 ciphers instead of DES,
would we have been better off? How? Were we just lucky that
DES was as secure as it appears to be?
------------------------------
From: [EMAIL PROTECTED] (Gregory G Rose)
Subject: Re: lfsr - polynom
Date: 12 Jan 2000 17:25:09 -0800
In article <85i5jh$335$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
>My problem is, to choose feedback polynoms
>for a stream cipher system consisting of
>lfsr.
The cipher system must consist of more than just
LFSRs. You need nonlinear state functions,
irregular stepping, or other methods to confuse
the outputs.
>In which way i find a suitable polynom?
>Rueppel write in his book (analysis and design
>of stream ciphers) to choose a polynom which
>produce random sequences which lin. complexity
>is near to his period length. Is this rigth?
No, that's not right. The linear complexity of
the output of an LFSR is, by direct observation,
the same as the degree of the polynomial, which
is very much less than the period of the output.
The period can be as high as 2^n - 1 for an n-bit
LFSR. It is the other things mentioned above that
contribute to the increase in linear complexity.
>In other books the use of primitive polynoms
>is recommended. Primitive Polynoms produces
>m-sequences which period length ist very differnt
>from the lin. complexity of such a sequence.
I think you've misinterpreted Rueppel. This
statement is correct. Note, however, that these
other books are not recommending that you actually
use the output of the shift registers directly...
just that primitive polynomials make the best
building blocks.
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: Michael Sierchio <[EMAIL PROTECTED]>
Subject: Re: Blum, Blum, Shub generator
Date: Wed, 12 Jan 2000 17:27:04 -0800
Kent Briggs wrote:
>
> I've been playing around the Blum,Blum,Shub generator and was
> wondering how to calculate the period for a given n=pq. For
> example, using small numbers like p=19, q=23 (both congruent
> to 3 mod 4), the generator will spit out 30 numbers in the
> sequence defined by x = x^2 mod n before repeating. The period
> increases as n increases but I've yet to figure out the exact
> correlation. Anyone know?
1) Read Terry Ritter's comments here:
http://www.io.com/~ritter/NEWS2/TESTSBBS.HTM#BB&S
http://www.io.com/~ritter/ARTS/CRNG2ART.HTM#Sect4.4
2) All BBS generators have multiple cycles, and all have some
short cycles. The best you can do is construct one that is
guaranteed to have long cycles. This means that it is not
sufficient to choose p,q == 3 mod 4, but also p & q of the
form
p = 2*p1+1, p1 = 2*p2+1 p,p1,p2 prime, and
q = 2*q1+1, q1 = 2*q2+1 q,q1,q2 prime, and
only one of p1, q1 has 2 as a quadratic residue.
3) You can't seed a BBS generator with random data and not risk
selecting a number that is on a short cycle, AFAIK.
--
QUI ME AMET, CANEM MEUM ETIAM AMET
------------------------------
Date: Wed, 12 Jan 2000 01:39:14 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Square root attacks against DSA?
=====BEGIN PGP SIGNED MESSAGE=====
"Paulo S. L. M. Barreto" wrote:
>
> In article <[EMAIL PROTECTED]>, David says...
> [...]
> >lcs Mixmaster Remailer wrote:
> [...]
> >> The problem is that "mod p mod q" does not define a group structure.
> >
> >You're right, the attack doesn't work.
> [...]
>
> So the only effective attack known up to now seems to be the following
> idea suggested by Serge Vaudenay:
>
> >There is still a square root attack which consists in collecting 2^80
> >(r,k) pairs in a hash table (sorted by the first entry), and waiting
> >for a signature with an r in the table. [...]
There is another attack that allows creating colliding messages, such
that a signature on one will be a valid signature on another. This
is because the hash function is effectively h'(x) = h(x) mod q, so
we can find collisions in h' with work sqrt(q). Credit goes to
Serge Vaudenay for this attack as well:
Serge Vaudenay,
"Hidden collisions on DSS,"
Advances in Cryptology - Crypto '96, Volume 1109 of Lecture Notes in
Computer Science, pp. 83-88. Springer-Verlag, 1996.
ftp://ftp.ens.fr/pub/reports/liens/liens-96-9.A4.ps.Z
Whether this type of collision is a problem depends on the application,
but it probably would be a problem if the signatures are relied on to
be non-repudiable, rather than just for authentication.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOHvbJTkCAxeYt5gVAQGJKQgApNQwxKq48XyCP0fyZlpPu65owJGz0uYn
7QoY02GNzTw781FH+lviEiJmGtM8qEw23GIEFOc9/MQWUW/5FSPbfoBHmCQfEJ9f
3dIocHXH/ccsjt2pAtPBTm4+EMpZdSZLr9d9dUnZT7s9oe5wgFB80H5AZ6NhTmlW
zRNK7471VA95Ps7uQyYUTYN1uKNJ/Bf9G6H0F4TRV3L/j+Jcy78l3JQSKBMKeQjA
l/zqMBG3mJhzXKUUlfmUWQ74m+kCh9hjJIZ1xrtv+SQuM487LJ9PMAjurumCyFMK
HpIc9K8DdEhLpSAqkKpReQIb1Ukjj656uIeaIesJg9VV25kNoLRywg==
=T16i
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Questions about message digest functions
Date: Thu, 13 Jan 2000 01:50:06 GMT
Tim Tyler wrote
> [EMAIL PROTECTED] wrote:
> : Tim Tyler wrote:
> :> Recall that I calim that each hash value should occur
> :> with as near-equal frequency as possible given the
> :> target distribution of message files to be hashed.
> :>
> :> A classical pseudo-random function would produce something
> :> more like a bell-shaped distribution.
>
> : First, to be have any meaning at all you have to
> : say what random variable you think to have a
> : bell-shaped distribution. [...]
>
> Domain: possible hash values corresponding to plausible messages;
> Range: the frequency of the occurrences of each hash value.
Ah - there's the problem.
Given the function
f(x) = number of messages m (of some limited
length) such that x=hash(m)
I agree a hash is bad if f(x) is bell-shaped.
But you are simply wrong: it is _not_ expected to be
bell-shaped for a random function. You can test it for
small ranges. You'll find the graph is jagged but stays at
roughly the same height.
> : Second for the meaningful statistics that we could use, it's the
> : variance that indicates how nearly-equally frequent the digest
> : are, not the shape.
>
> I generally agree. However, a near flat distribution is always
> the ideal, and a bell-shaped distribution almost always fails to
> be as good, pretty much regardless of the variance.
Nonsense, probably deriving from not knowing what
distributions are bell-shaped.
[...]
> :> When the messages to be hashes are much longer than the hash, the
> :> hashes will still follow a bell-shaped curve, rather than being a
> :> near-flat distribution.
>
> : You lost me. You say the distribution function is
> : bell-shaped for a random function, and flat for a
> : function in which each digest has the same number
> : of preimages? What random variable are talking
> : about?
>
> I've varied this reply rather than repeat it verbatim:
>
> Domain: all possible hash values;
> Range: the frequency of the occurrences of each hash value.
The point of those questions was to bring up the
misunderstanding. If you graph f(x) = frequency of digest
value x, the graph is perfectly flat if each digest has the
same number of pre-images, but it is not bell-shaped for a
random function.
Another graph we might draw to describe the distribution is
g(x) = number of digests having x pre-images.
That would be bell shaped for the random function. But the
flatter the bell the _less_ evenly the preimages are
distributed to the digests. Low variance in the number of
preimages corresponds to a tall thin bell.
Random functions have the distribution we want for a hash.
As message size increases, the variance in the number of
preimages vanishes in proportion to the mean. For messages
of arbitrary size, the graph you named looses its
jaggedness; it becomes the flat line you want and not the
bell you thought.
Now look at the requirements for a cryptographic hash
function. It maps a preimage of _any_ size to a fixed-size
digest. Collisions and preimages are not limited to small
sizes. Hash functions work with messages of arbitrary size,
and for messages of arbitrary size the distribution induced
by a random function is the ideal.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: "1:1 adaptive huffman compression" doesn't work
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jan 2000 02:12:00 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> :> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
:> :> : I am not quite sure whether one couldn't even attempt to 'define'
:> :> : the 1-1 problem away with a 'convention'. That is, if on compression
:> :> : the last code symbol does not fill to a byte boundary, then the
:> :> : software has to do filling with bits that do not form a valid code
:> :> : symbol and it is 'required' by convention that the filling is
:> :> : to be random, say dependent on the system clock. [...]
:> :>
:> :> This is pretty much the same technique as John Savard proposed.
:> :>
:> :> It works to the extent that you can generate genuinely random bits.
:> :> If your bits are not completely random then you still have problems.
:> :>
:> :> You also wind up with a non-deterministic compressor. The system
:> :> fails to exploit the range of the compressor to itsgreatest possible
:> :> extent. It is no longer portable to embedded environments with no
:> :> obvious reliable source of genuinely random noise available.
:>
:> : No.
:>
:> Yes.
: My 'No' was intended to negate your 'no longer portable', not
: 'non-deterministic'. Tell me in what sense the software is not
: portable?
If you have no convenient source of genuine randomness, it won't work.
Not every system comes with a good hardware source of random numbers.
If you use something pat all redictable, you introduce possible problems.
Whatever, not even something like Java has an interface for generating
"real" randomness in a portable manner, AFAIK. There's the
"SeederDialog" - but you can hardly use that in your compression routine.
You're probably going to have to use different methods of getting
randomness on different systems.
:> : Whether the software on two runs of compression put in the
:> : same bunch of (supposedly) random bits is of no significance.
:>
:> It makes little difference to security - if the padding is genuinely
:> random. But it may not be of *no* significance overall. For example it
:> prevents the end user from checking whether two files deccompress to
:> identical results by using the "diff" program on the compressed files.
:> Very few things are of no significance at all.
: I mean the 'significance' in the context which Scott raised with
: his 1-1 concept. In that context the difference is of no significance,
: because it tells the analyst nothing (and in fact
: it tells him nothing for the very reason that there are very
: often differences.)
Um, what about my example?
: Besides, did you actually mean 'compress' insteaed of 'decompress' in
: your last but one sentence above?
I did not. I meant "decompress", instead of "deccompress", though ;-)
: (Decompressing is by construction o.k.! Only the compressed files
: may be different due to the different filling bits.
Yes, but the user can't check if two compresssed files are the same by
using diff on the compressed files. He'd have to decompress them first.
: If you want to check whether two compressed files have the same 'content',
: decompress these and then apply the 'diff'.)
What if your user then tells you this is a pain in the ass, and is causing
him to fart around deleting files unnecessarily to save space?
I bother to make this point only to illustrate that random padding may not
be "of no significance".
:> As a sample security concern, compressing the file and encrypting it
:> will no longer produce the same result.
:>
:> This means if the file gets lost and you have not stored a local copy you
:> may wany to recompress and reencrypt, using the original key.
: Normally
:> this will involve few security problems, as eavsdroppers gain little
:> additional information from the identical cyphertext. However a "random"
:> compressor ending gives them two files, encrypted with the same key, with
:> a few bits of plaintext differing between them.
: If you have a 1-1 compressor and 'the file gets lost and you have
: not stored a copy', what do you do? You have to do the same amount
: of work, don't you? What is the 'plaintext' of 'a few bits of
: plaintext differing ...' above?
The compressed file. This has a few bits different where the padding is.
: Isn't that what you called 'plaintext' random?
I'm not sure how to parse this question. I /think/ the answer is "no",
but would have to see a clarification of what is being asked to say for
sure.
: So what kind of information the analyst possibly could
: get from that random stuff?
Like I said it may provide information about the type of encryption used.
It might tells an attacker that information doesn't diffuse backwards
through the file. The distance from the start of the message at which the
corruption occurs may provide information about the block size which he
did not previously posess.
: Could you give some detailed description of how he could exploit
: such random 'plaintexts'?
He can get information from them relating to the encryption which would
not have been available had a deterministic compressor been employed.
:> This may give the attacker information about - for example - the block
:> size being used, which he did not have from the original message alone.
: What do you mean by 'block size' here?
The size of the block used for encryption with a block cypher.
Say we have a two messages that are a multiple of 128 bits long that
differ in one corrupted section, which starts and ends a multiple of 128
bits from the start of the file. The attacker might immediately think
"aha, 128-bit block cypher, ECB mode". However there is more corruption
at the very end of the file, caused by non-deterministic compression
ending. This scrambles a block of data that starts a multiple of 64 bits
from the start of the file.
The attacker can now think - AHA - 64 bit block cypher with coincidental
resembalance to 128-bit block cypher!
In principle this sort of information might result in an identification
of which party the message was sent from, if it could have come from a
number of different locations which use different forms of encryption.
This is traffic-analysis - style information - which should not be sneezed at.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
May all your PUSHes be POPped.
------------------------------
From: Thierry Moreau <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Blum, Blum, Shub generator
Date: Wed, 12 Jan 2000 21:40:27 -0500
Kent Briggs wrote:
>
> I've been playing around the Blum,Blum,Shub generator and was
> wondering how to calculate the period for a given n=pq. For
> example, using small numbers like p=19, q=23 (both congruent
> to 3 mod 4), the generator will spit out 30 numbers in the
> sequence defined by x = x^2 mod n before repeating. The period
> increases as n increases but I've yet to figure out the exact
> correlation. Anyone know?
Certainly those who can read the original BBS article know.
>
> --
> Kent Briggs, [EMAIL PROTECTED]
> Briggs Softworks, http://www.briggsoft.com
Here is the general algorithm:
-- Parameter selection --
Select N=P*Q, P and Q are distinct prime numbers congruent to 3 mod 4
(actually Hugh C. Williams was the first mathematician to propose such
numbers for public key crypto, early in the development of the field).
-- Parameter-related precomputations --
Compute lambda(lambda(N)) from the definition of the "lambda function"
in the original article. This requires you to know every prime divisors
of (p-1) where p is a divisor of (P-1) and/or (Q-1).
The BBS period is a divisor of lambda(lambda(N)), so you should make a
sorted table of every possible divisors (prime and composite) of
lambda(lambda(N)).
-- Seed selection --
(a) pick a number X from 1 to N-1 inclusive
(b) reject any multiple of P or Q (there are (P-1)(Q-1) candidates left)
(c) compute X0=X^2 MOD N; this is a "quadratic residute"
(d) given this X0, find the smallest divisor of lambda(lambda(N)) that
happens to be the period (you can check whether a given number is the
period using the algorithm to jump ahead the BBS sequence from the
original article)
(e) if the period is too short for your purpose, go back to (a)
(f) if the period is too short too often, consider another N
-- Hint --
Pick up N=(4*p+3)(4*q+3) where p, 2*p+1, 4*p+3, q, 2*q+1, 4*q+3 are all
prime numbers (the original article adds another hint about 2 NOT having
some number-theoretic property relative to both 2*p+1 and 2*q+1, or
something like that, but you may decide to ignore this in favor of
observations on the probability distribution of actual periods). Then
you may get a period of 2*p*q most of the time. When you do, it's
because there are exactly 4*p*q+2*p+2*q+1 quadratic residutes and two
BBS sequences of length 2*p*q make up for the vast majority of them.
Disclaimer: If I can digress all of the above based on the study of the
original BBS article, others certainly do!
-- Incidentally ...
Concerns about short periods for the BBS generator when used for
cryptographic applications are analogue to the "iterated encryption
attack" on the RSA cryptosystem. Those who seriously studied the
generation of large prime numbers for public key cryptography (e.g. Ueli
Maurer) usually recommend to ignore the "iterated encryption attack" on
the RSA and I wonder whether their advice would turn into an advice to
ignore the above hint on BBS parameter selection if they had a chance to
study the BBS parameter selection. There never seem to be a "final say"
on the theoretical aspects of public key cryptography.
Have fun.
- Thierry Moreau
[EMAIL PROTECTED]
web site: http://www.connotech.com
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Blum, Blum, Shub generator
Reply-To: [EMAIL PROTECTED]
Date: Thu, 13 Jan 2000 02:18:35 GMT
Kent Briggs <[EMAIL PROTECTED]> wrote:
: I've been playing around the Blum,Blum,Shub generator and was
: wondering how to calculate the period for a given n=pq. For
: example, using small numbers like p=19, q=23 (both congruent
: to 3 mod 4), the generator will spit out 30 numbers in the
: sequence defined by x = x^2 mod n before repeating.
I presume the period depends on the initial x. Consequently, any
calculation of the period from p and q will be probabalistc.
>From what I understand, there are a number of other (more complex)
properties of p and q which affect the expected period of the generator,
besides congruence to 3 mod 4.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
The early worm gets the bird.
------------------------------
** 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
******************************
