Cryptography-Digest Digest #32, Volume #12 Thu, 15 Jun 00 02:13:01 EDT
Contents:
Re: Cryptographic voting (zapzing)
Re: small subgroups in Blum Blum Shub (Nicol So)
Re: Evidence Eliminator Dis-Information Center (EE Detractor)
Re: Finding prime numbers ("Scott Fluhrer")
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: Random sboxes... real info (David Hopwood)
Re: hmac and 'length' issues (David Hopwood)
Re: Comments/analysis requested: stream cipher derived from hash (David Hopwood)
Re: On using compression as proper means of encryption (David Hopwood)
----------------------------------------------------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Thu, 15 Jun 2000 04:12:21 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> Back to crypto voting, I'm going to point out something that is a
slight
> variation of what has been discussed.
>
> When you register to vote, which, at least in Florida you must do
> in person, you could be issued a key pair. They would fill out
> the registration card on paper. You would then go over to a computer
> and get your random key pair, the public key key would be registered
> by the computer as "in use" but your name would not be attached,
although
> a "registered to voter 193687" could be also issued, with the 193687
> just being a number that has no links to a specific individual.
The real problem would probably be that there would be
nothing stopping someone from registering in one place,
then going somewhere else and registering there.
> When it came time to vote you would encrypt with your private key
> and send it in, the voting list could then be published on the
> net and you could verify your vote is what you voted.
>
> The real problem with digital voting is the domineering spouse
> scenario. You can never be sure that the person is voting free
> of coercion, their spouse could be looking over their shoulder
> telling them how to vote or could even be doing the voting for
> them.
\
How about this: when you register you specify a
string of random number that your vote should
be xored with. Then you lie to your spouse about
what that string was. This could require a trusted
party though.
> Now, obviously this isn't going to work in California, but most
> of the rest of the country doesn't support voting fraud and it
> should work there.
>
> Roger Books
> ---------------------------------------------------------------------
> | Unix sysadmin for food, LF photography and miniatures |
> | wargames for fun. [EMAIL PROTECTED], http://www.jumpspace.net |
> ---------------------------------------------------------------------
>
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 00:56:45 -0400
Reply-To: see.signature
tomstd wrote:
>
> I don't know why people still consider the BBS generator. It's
> not very safe.
I'm not aware of any real-life application that uses it. I think the BBS
generator is mostly of theoretical interest only. It is interesting
because it has some well-understood properties--for exmaple, its
security is (demonstrably) reducible to a well-known intractability
assumption.
On what basis did you come to the conclusion that it is "not very safe"?
> Let's ask some questions:
>
> 1. How do you use it? Well construct "special" primes and use
> a relatively prime root. I have seen to use 3 mod 4 primes and
> p- strong primes...
>
> 2. What is the period? Gosh-geez I dunno, pretty darn big!
The overwhelming probability that a randomly chosen element will fall on
a long cycle is an automatic consequence of the underlying
intractability assumption, if you accept it. (If you don't, the security
proof is just another interesting intellectual exercise).
> 3. How fast is it? Well at 2kb/sec we now have the fastest
> prng.
>
> Woopy. It's hard to use, big and slow. BAD IDEA!
You may dislike the BBS generator for its inefficiency, but how many
*rigorous* analytic results can you find about the behavior/security of
actually deployed PRNG's can you find?
--
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: EE Detractor <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.firewalls,alt.privacy.anon-server,alt.privacy
Subject: Re: Evidence Eliminator Dis-Information Center
Date: Wed, 14 Jun 2000 23:04:25 -0500
On Wed, 14 Jun 2000 19:33:00 -0700, [EMAIL PROTECTED] wrote:
>
>
>EE Detractor - speaking for us all, protector of newbies, patron saint of
>widows and small children
>EE Detractor-ooney, making coffee....
Nah, just so bored with Usenet that I've taken to playing with trolls.
:-}
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Finding prime numbers
Date: Wed, 14 Jun 2000 22:00:33 -0700
Anton Stiglic <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tony T. Warnock" wrote:
>
> > > then you need to show that the gap between a prime p and next prime
(the
> > > number of loop iterations) is bounded by a polynomial in log(p). Now,
> > > looking at prime gap tables, that appears to be very likely, but I
didn't
> > > anyone has proven that.
> > >
> > > If that has been proven, could someone enlighten me? If you are
thinking of
> > > a different next-prime algorithm, could you enlighten me?
> > >
> >
> > One does have the theorem that there is a prime between P(k) and 2P(k),
also
> > there is a prime between P and P**c for (I think) any c>1+epsilon.
>
> Even better: there is a prime between p and p + 1/5p, for primes p > 9.
> and there is a prime between p and p + 1/13p for primes p > 11
Huh? Setting p=13, there is a prime between 13 and 14?
(Actually, that should be for integers > 117. In addition, the website
listed below appears to claim it's true for > the 118th prime number (647),
which is correct, but not the lowest possible bound).
> and even tighter gaps for bigger n.
> See
> http://www.utm.edu/research/primes/notes/gaps.html
>
> but these gaps are polynomial in p, not log(p).
>
> Define g(p) to be the number of composites between p and the next prime.
> There are interesting results and conjectures on bounds of g(p)/log(p).
> Again, see
> http://www.utm.edu/research/primes/notes/gaps.html
> for example.
Interesting site. Thanks. Still doesn't invalidate my claim (that there is
no proven bound on g(p) which is polynomial in log(p)).
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Thu, 15 Jun 2000 05:32:53 GMT
On Wed, 14 Jun 2000 23:56:51 -0400, in
<[EMAIL PROTECTED]>, in sci.crypt Nicol So
<[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>>
>> On Wed, 14 Jun 2000 18:08:23 -0700, in
>> <[EMAIL PROTECTED]>, in sci.crypt lordcow77
>> <[EMAIL PROTECTED]> wrote:
>>
>> >Essentially, the existence of exploitable cycles in BBS would
>> >neccesarily lead to an efficient algorithm for decomposing RSA
>> >moduli into primes. As such, if you believe that the factoring
>> >of numbers in that range is a difficult problem, you need not
>> >loose sleep over the miniscule probability that you will land in
>> >a short cycle. The nonsense about choosing "strong primes" or
>> >good initialization values is a remnant to the past where it was
>> >thought that a relatively small prime (if well chosen) would be
>> >adaquately strong.
>>
>> I think your interpretation is wrong, and I recommend the BB&S paper
>> to you:
>>
>> Blum, L., M. Blum and M. Shub. 1983. Comparison of Two Pseudo-Random
>> Number Generators. Advances in Cryptology: CRYPTO '82 Proceedings.
>> Plenum Press: New York. 61-78.
>>
>> BB&S did expect large primes; the requirement for "special" primes was
>> to guarantee that the system had cycles of some long, known and
>> computable length. The existence of cycles of known length made it
>> possible to efficiently check that any particular initial value x0 was
>> on such a cycle, and to choose another x0 if not. Short cycles
>> certainly do exist in BB&S, and short cycles are "exploitable." The
>> selection procedure thus eliminates the possibility that x0 is on a
>> short cycle, and so provides a *guarantee* of that form of strength.
>> That sort of a *guarantee* is simply not present when we just choose
>> x0 at random and hope for the best, even if x0 is very, very likely to
>> be on a long cycle.
>
>lordcow77's interpretation is correct. The safety of using randomly
>chosen primes of appropriate sizes is built into the underlying
>intractability assumption. To put things in perspective, the whole point
>of using cryptography is to reduce the probability of "bad things
>happening" to some acceptably low level, say 2^{-L} for some
>sufficiently large L. (There's no defense against dumb luck on the part
>of the adversary). Not using special primes may affect the value of L
>for a given choice of security parameter (so you may have to adjust your
>security parameter), but it does not affect the asymptotic behavior of
>security as a function of the security parameter.
"To put things in perspective," I suggest you try to follow my
reasoning before trying to refute it.
As you would have seen had you actually read and understood my
comments, the statement in question was:
>> >The nonsense about choosing "strong primes" or
>> >good initialization values is a remnant to the past where it was
>> >thought that a relatively small prime (if well chosen) would be
>> >adaquately strong.
And that is nonsense. I am unaware of any such "thoughts." Exactly
where do you disagree, and what is your evidence?
On the other hand, the larger question of X^2 mod N security (not part
of my earlier comments) is swept under your asymptotic rug. But real
systems are *not* asymptotic. All real BB&S systems *do* have short
cycles. And short cycles *are* weak. Yes, it is unlikely to select a
short cycle at random. But unless the BB&S prescriptions are
followed, that is *only* "unlikely" and *not* "impossible." In
contrast, the BB&S prescriptions *guarantee* that one does not use a
short cycle, and that is a qualitative difference.
As I see it, the issue is *not* strength in practice, it is instead
the claim to have a provably secure system. I think we can accept
that all cryptography is vulnerable to opponents choosing the right
key at random. But I claim that no system can be provably secure if
it includes the possibility of selecting and using weakness, no matter
how small that possibility may be.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
Date: Thu, 15 Jun 2000 03:12:08 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Random sboxes... real info
=====BEGIN PGP SIGNED MESSAGE=====
Tim Tyler wrote:
> David Hopwood <[EMAIL PROTECTED]> wrote:
> : tomstd wrote:
> :> Well those 2^128 permutations out of the entire (2^64)!
> :> permutations are strong with respect to diff and linear
> :> analysis.
>
> : I think you may be labouring under a misapprehension - the 2^128
> : permutations selected by the key are not stronger than a permutation
> : selected at random from the entire space of (2^64)! possibilities.
> : In fact, a method for selecting a permutation uniformly at random
^^^^^^^^^^^^^^^^^^^
> : from that space would be as secure as a keyed permutation (a.k.a.
> : block cipher) of that size can possibly be.
>
> That last seems questionable.
Not at all.
> The space of all possible permutations contains the identity
> transformation - which is not strong.
It is not specific permutations that are strong or weak; it is the
method of selecting them. The identity transformation occurs with
probability 1/((2^64)!), which is exactly the probability that it
*should* occur with for a maximally secure block cipher.
Worrying about a permutation selected uniformly at random (if it were
possible to do that) being weak, is just as bogus as worrying about
a perfectly implemented OTP having an all-zero keystream. Not only
is it not a practical weakness, it is not a theoretical weakness
either: the identity transformation occurs with the probability we
would expect for a keyed permutation that hides all information about
its input.
- --
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
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOUg7QzkCAxeYt5gVAQEpQAf+KoRq6yj8ZdR7dg51WfngRxHFypZQfAo5
xzoJPQYt3wvzPsICmxXfxBUE38uTELJeJx6vjSSGPw8t2HZw8LLGzErhlhdW6C2C
3B3w3zTV0zslE3NXmNtPY4VKyY1RKXszMJ4FNEmt4igHL4vbrlVm+az4YidL8HsC
bgUUJFABwfuvu1adzJbXJPRVEQDo8RN95MX8XMf9ABv+wKg2BYsTUZ8SEsLWEgD8
6ovU2h6vAWP4ymMGGFBGPndNfChleVp27RvkIMgH9cIY9eiuPXFTns6W1oITIaOX
HfN7njrF7mGwSreo6o7HZEZ5EbRNenZpYRGG9n6REmQ6e1Vma4L8Gw==
=nhDw
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 15 Jun 2000 02:51:48 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: hmac and 'length' issues
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
>
> One common problem with using keyed hashes as MACs is that additional
> data could be appended (or pre-pended, depending on the algorithm) with
> the required hashing easily performed.
>
> From what I have seen of the HMAC construction, it doesn't need a length
> field to help prevent this sort of attack, but I would sure like some
> consensus to that effect from other cryptoheads before implementing it
> without a length field.
HMAC prevents this type of attack because a direct hash of the message
is not exposed:
HMAC_H(key, text) = H(key XOR ipad, H(key XOR opad, text))
I.e. because H(key XOR opad, text) is not accessible to an attacker,
it isn't possible to use it to construct the hash of a longer message.
- --
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
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOUg2kzkCAxeYt5gVAQElJQgAlbieEPMSh5zveG0hewbwcFzcyY3SQiJC
ik24U5pj5Qf+kgA6PN6bU8rIACK9AilIonbNbOE39Gqqqa69wvzoNeQHK1k7Rvn8
Qd7adts7/UQT6Jlj+GnVC+WR+Udq6+LCNGX2tIBqxgYlcJp3r+CiVpG4P1I4sZ+l
9ck+mDy4nrkiMKGeld7ju/HqmgOjelKeniR7SY4MgA7kJ5RmH32s/hfzaBOF1C8D
Ueqdev1T5ZfE/7tF7nqT+PrxBCA2Oeg2bXCSvJxW1spFBXuE4UsfD8C9fTanyaom
RVR/61wdX7ZADxqmwHrr/kD+tLO8v/OeH+/MhDyr+Wr6gYkwsRWpDg==
=4WQq
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 15 Jun 2000 03:26:27 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Comments/analysis requested: stream cipher derived from hash
=====BEGIN PGP SIGNED MESSAGE=====
Lon Willett wrote:
> Notation:
> N -- size of hash function output
> B -- size of hash function block; must be >= N.
>
> hash(S: DATA) -- cryptographic hash compression function that maps
> the N-bit value "S" and the B-bit value "DATA" to an N-bit value
> (e.g. "hash" is SHA-1, "N" is 160, and "B" is 512).
>
> State (after N*i bits output):
>
> S1[i], S2[i] -- N-bit values
>
> Iterative step (generate the next N bits of output):
>
> Output[i] = S1[i] xor S2[i]
> S1[i+1] = hash(S1[i]: S2[i])
> S2[i+1] = hash(S2[i]: S1[i])
If S1[i] is ever equal to S2[i], the output after that point will lock to
all-zeroes. The probability of that happening at each iteration is 2^-N,
so the expected number of iterations before it happens is on the order
of 2^(N/2). This is a mostly theoretical weakness when N is 160 (and
definitely theoretical when used in your RNG), but in any case, it can be
fixed by making the two hashes different, e.g.:
Output[i] = S1[i] xor S2[i]
S1[i+1] = hash(S1[i]: S2[i], 0)
S2[i+1] = hash(S2[i]: S1[i], 1)
In this case, if 'hash' can be treated as a random function, then
(S1[i], S2[i] -> S1[i+1], S2[i+1]) is also a random function, which would
imply an expected cycle length of about 2^N.
It would also be possible to add the counter i to the hash input; that
guarantees an effectively unlimited cycle length.
> Other RNGs seem to assume that enough entropy can be collected before
> they remix their pools to prevent backtracking attacks. I would like
> to make backtracking attacks "hard", even in the absence of any new
> entropy, and this seems to be the simplest way of doing it.
Yes, I completely agree with this.
[...]
> But I am still very interested in how
> strong it remains when both "E[i+1]" and "H[i+1]" are missing (zero),
> but the initial values for S1[0] and S2[0] are strong.
[...]
> Input:
> E[i+1] -- N-bit miscellaneous entropy data (if available, else zero)
> H[i+1] -- N-bit hardware RNG generated value (if available, else zero)
>
> Notes:
>
> H[i+1] may be weak (or zero), or may be known to an adversary,
> but CAN NOT BE MANIPULATED by the adversary (ideally, of course,
> it is none of these things).
It's generally a good idea in RNG design to assume that the entropy input
*could* be manipulated, at least partially.
> There are no restrictions on E[i+1], but if it doesn't contain a
> full N bits of entropy, then the PRNG is susceptible to an
> iterative guessing attack, and so it shouldn't be used. Rather,
> it should be saved and combined with more entropy sources until
> at least N bits of entropy have been accumulated. And, of
> course, ideally it should be unknown and unmanipulated by
> attackers.
>
> Output:
>
> New state:
> S1[i+1] = hash(S1[i]: S2[i], E[i+1])
> S2[i+1] = hash(S2[i]: S1[i], H[i])
> H[i+1]
>
> Random value (N bits):
> Output[i+1] = S1[i+1] xor S2[i+1] xor H[i+1]
I'd change that to:
New state:
S1[i+1] = hash(S1[i]: S2[i], i, 0, X[i])
S2[i+1] = hash(S2[i]: S1[i], i, 1, X[i])
where X[i] is taken from both the hardware RNG and the other entropy
sources, whenever a conservatively estimated N bits of entropy have been
collected, and X[i] is the empty string on iterations where not enough
entropy has been collected. I don't think there is any need to treat the
hardware RNG input and the other entropy input differently.
Random value (N bits):
Output[i+1] = S1[i+1] xor S2[i+1]
I removed the XOR of the output with H[i+1], because it allows state
following attacks (what you called iterative guessing attacks above) if
each H value is of low entropy, and all E values are of zero entropy.
If you're concerned with this type of attack, it's better to mix in
entropy only in fairly large chunks.
- --
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
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOUg+jDkCAxeYt5gVAQFiTQf9HfJw9R+2yXAAOOdc4jM+8txrVdMl5OmA
fgBORNPLd+4r6enEdPWf/EYEvMuxGJw0AEbbquiznysGUHjJFBxLFY6zlM5D1+1Q
Zcm5pRbBCm38cNwEVjZY6yosa/E931p8iTfi1Ux6KQ/mQe0nC8Jm6TxUKjpGphMl
wp8LMmb4/kLY8f6WMrWMItjQ/YH7EYavioUpc0UppbNj0wBeLoDN/gMZi9iHt++d
3YVPzQziYU3SvhKfIyyG0Cw/Qw200SRKSt2w3cYUMjdPqVa+121s0LHFS2DG8uqK
+X9kI5lIzqRfPsYiqAr11BYvlR/sB8HE2cz20/NMv00SGCcJb5tQqA==
=ZOQZ
=====END PGP SIGNATURE=====
------------------------------
Date: Thu, 15 Jun 2000 02:24:26 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: On using compression as proper means of encryption
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
[snip]
> Use a PRNG (crypto strength unessential) with a key as
> seed to generate a sequence of symbols (length of sequence
> determined by PRNG) to initialize an adaptive Huffman
> compression algorithm, taking care that all symbols of the
> plaintext alphabet are input at least once. The output in
> this initialization phase is discarded. Then start feeding
> symbols of the plaintext into the algorithm. Use the result
> as ciphertext. Decryption amounts to a corresponding
> decompression after doing the same initialization.
This is very weak. It amounts to no more than a simple
substitution on variable-length symbols. Frequency analysis
can be applied almost as easily to variable-length symbols as
it can to fixed-length symbols.
[...]
> One can employ the scheme alone or as a component of a
> larger scheme (multiple encryption), where we note that it
> need not necessarily be the first component of the whole (as
> compared to current usage of compression as pre-processing).
If it is not the first component, it will expand the ciphertext
for no real benefit.
> One can also substantially boost up the scheme described
> above with simple add-on's. Since a PRNG is available to us
> anyway, I suggest that for this purpose we inject into the
> output stream of compression some amount of random bits
> at dynamically determined time points with the aid of the
> PRNG.
This does not provide any significant improvement, since the
"random bits" would have to not collide with any valid Huffman
output symbols (in order to allow them to be recognised by the
receiver), and the fact that they have different frequencies
to the valid symbols would allow them to be stripped out.
- --
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
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOUgwJjkCAxeYt5gVAQH9Tgf9Ez9BF/yThgwaloZhU7aSS0apdoAvocsp
lBOfLBG9qm/IMwwYuMoO/GR+HKe3fQdSItS7Raf6clLWQ1vgVNVq6FJb53aueH6P
qU2W34vpX84RM1HtDv1dFgtVxq66fG75b/XzrC08hPmvM2CHoDCFG1M6FpOqjUAu
aE6pmDmo3/wvDPB6gj8UUpaIyJtyD83FAClrtILF7/mPrliu8JsPlCh0KJEbBO2n
3fZ8JfxnlhQpuuoDcmqg4nyf/IZp14wKyJDX32DIjK/DeNGdrEkG8HROtkd4DQN4
oh8asKlHowu4NXPtbHnt3YCF5pMEAIJAjnSYMw7Xn+bGofpbtl9EKQ==
=L0NT
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
