Cryptography-Digest Digest #865, Volume #10 Fri, 7 Jan 00 18:13:02 EST
Contents:
Re: Why the Cryptonomicon in Cryptonomicon? ([EMAIL PROTECTED])
Intel 810 chipset Random Number Generator (Bradley Yearwood)
Re: Questions about message digest functions ("Matt Timmermans")
Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?) (David A Molnar)
Re: How about this for a "randomly" generated bitstream? (Terje Elde)
Re: Square root attacks against DSA? (David Hopwood)
Re: Square? (David Hopwood)
Re: Anonymous Source Problem (David Hopwood)
Re: Anonymous Source Problem (David Hopwood)
Re: Unsafe Advice in Cryptonomicon (Steve K)
Re: Wagner et Al. (wtshaw)
Re: How to pronounce "Vigenere"? (Dan Day)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Why the Cryptonomicon in Cryptonomicon?
Date: Fri, 07 Jan 2000 22:01:35 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (John Savard) wrote:
> On Tue, 04 Jan 2000 07:15:16 GMT, [EMAIL PROTECTED]
> (John Savard) wrote:
>
> [of the non-existence of 26 letter sentences with every letter...]
My favorite, since it can actually be parsed and mean something, is
Quartx glyph job vex'd cwm finks.
meaning roughly "the graffiti on the crystal irritated the traitors of
the glacial valley."
-Lou Scheffer
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bradley Yearwood)
Subject: Intel 810 chipset Random Number Generator
Date: 7 Jan 2000 14:13:16 -0800
In response to a recent inquiry, Intel have been kind enough to point out
that they have released a Programmer's Reference Manual detailing access
to the hardware Random Number Generator feature in the 82802 FWH (Firmware
Hub: BIOS Flash) chip in their 810 chipset. This document (their #298029-001)
may be found under the following page:
http://developer.intel.com/design/chipsets/manuals/
Whether the raw output from the hardware register is sufficiently
unbiased and otherwise random for specific uses, this document does
not say. They do recommend running e.g. FIPS 140-1 tests on the output
after initialization.
One interesting observation is that the device requires a variable
amount of time to generate a new random byte. Availability of a new
value is indicated by a status bit. They recommend a timeout of 4.5ms
in polling this status, which appears to indicate a worst-case rate of
random byte production of around 222 bytes/sec.
A big Thank You goes to Intel for providing this information.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: Questions about message digest functions
Date: Fri, 7 Jan 2000 16:43:47 -0500
I missed the start of this thread, but as far as I know, there are no known
one-way permutations that can be shown to be permutations -- do you
actually know of one, Tim?
For instance: If I publish an RSA modulus and public exponent as a PRP, how
do I show that it _is_ a permutation without revealing private information,
at which point it would cease to be one-way?
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?)
Date: 7 Jan 2000 22:04:43 GMT
William Rowden <[EMAIL PROTECTED]> wrote:
> I, too, was a reading child. "Omnipotent" is logically "omni-potent"
> /om'nee poe'tent/, right? I also remember the quizzical look I
> received when I first said "annihilation," complete with two short
> i's. Why is that "h" there?
You're in good company. My freshman calc prof pronounced it the same
way. After a while I caught myself doing the same...
This same prof also had an unforgettable introduction to Markov
processes. "We will study the population of rabbits...and fish. In a very
strange world where the rabbits can not only eat the fish, but also be
eaten *by* the fish."
Thanks,
-David
------------------------------
From: [EMAIL PROTECTED] (Terje Elde)
Subject: Re: How about this for a "randomly" generated bitstream?
Date: Fri, 7 Jan 2000 22:40:44 +0100
In article <853ocm$[EMAIL PROTECTED]>, Guy Macon wrote:
>In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Terje Elde)
>wrote:
>>This ensures that if you get long runs of 0's or 1's or some other such
>>thing then it'll be discarded. Then again, if you get long runs of
>>0101010... you're in trouble again :)
>
>One problem: an audio recording that is accurate to the LSB sounds
>considerably worse than one with 1 LSB of random noise added. Because
>of this, it is common to add 1 LSB of random noise. In the old days
>this was usually resistor noise, but nowdays it is chaeper to write a
>psuedorandom generator program on the DSP chip in your mixing board.
>I doubt that the psuedorandom generator programs are at all suitable
>for crypto. (At last! My membership in the Audio Engineering Society
>finally paid off!)
This we should obviously check for this kind of thing before relying on it
for random bits =)
Anyways, the idea is basicly still the same, of a 16 bit recording you
could use the 3rd or 4th lowest bit, but I cannot scream loudly enough
that one should still not rely on a single random source. Sure audio can
be used as one input, but it's easy to affect, and you don't know how the
hardware is built, but it does make a good source of random data because
of the rapid datarate, so use yarrow, and mix in other sources, both high
and low speed ones. Disk activity, network activity (some would claim that
to be a stupid idea, I say read up on yarrow first).
Thanks for listening :)
Terje Elde
--
Hi! I'm a .signature virus! Copy me into your ~/.signature to help me
spread!
------------------------------
Date: Fri, 07 Jan 2000 21:37:06 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Square root attacks against DSA?
=====BEGIN PGP SIGNED MESSAGE=====
In message <000601bf5835$6206ff80$[EMAIL PROTECTED]>
"Paulo S. L. M. Barreto" <[EMAIL PROTECTED]> wrote:
[...]
> There's an additional limitation I didn't write down in my original
> question. Assume the attacker has access to the public parameters
> (p, q, g) and the signature (r, s) alone, not directly to the public
> key. This is the case, say, if the public parameters are shared by
> all users of an authentication system, the signatures are printed on
> a bill or invoice, but verification is only done through a restricted
> access terminal. As pointed out in in the coderpunks list, this has
> the same effect as using a MAC, since the "public" key acts as a
> shared secret.
I wouldn't assume that it's as secure as using a MAC, since signature
algorithms are not really designed for this (i.e. keeping the "public"
key secret). Another case of a protocol that relies on keeping a
public key secret is EKE, which in principle can be written in an
algorithm-independent way, but in practice requires all sorts of hacks
for specific PK encryption algorithms in order to avoid security
problems.
> Anyway, the goal is to attack the system given only the data
> mentioned above (so this is a rather theoretical question). It's not
> even necessary to assume q is small (index calculus faces the same
> problems as Pollard if y is unknown).
> My motivation for this question was that it is necessary to have
> *some* quantity of form g^u mod p to start an attack, but DSA only
> provides g^k mod p mod q (Schnorr provides hash (m || g^k mod p),
> which poses a similar problem), given that y is kept secret.
However, if we treat the "mod q" as acting like a random function
mapping from subgroup elements to 0..q-1, it's still possible to do
probabilistic versions of the square root attacks. With more than
one signature, candidates for the logarithm can be verified. For
example, here's a possible attack using a variant of baby-step
giant-step:
1. Obtain p, q, and g.
2. Obtain r_i, s_i, and h(m_i) for a small number of signatures
(2 should be enough), where (r_i, s_i) is a signature on m_i.
3. Compute w_i = s_i^-1 mod q.
4. Compute u1_i = w_i * h(m_i) mod q, and u2_i = r_i * w_i mod q.
(So far this is the same as DSA signature verification, for
each i.)
5. Compute beta_i = r_i * (g^u1_i mod p)^-1 mod q.
(For a valid signature, r_i = (g^u1_i * y^u2_i mod p) mod q.
Therefore (y^u2_i mod p) mod q = r_i * (g^u1_i mod p)^-1 mod q
= beta_i.)
6. Construct a table with entries (j, g^j mod p mod q), for
j := 0..m-1. Sort this table by second component.
(Alternatively, use conventional hashing on the second component
to store the entries in a hash table.)
7. Compute g^-m mod p mod q and set gamma := beta_0.
8. For i := 0..m-1,
8.1. Check if gamma is the second component of some entry in the
table.
8.2. If gamma = g^j then (im + j) is a candidate for log_g(y^u2_0).
Let x' = (im + j) * u2_0^-1 mod q, and check whether this is
the correct value for x by testing whether
g^(x' * u2_i) = beta_i for each i > 0; if these checks pass,
stop.
8.3. Set gamma := gamma * g^-m mod p mod q.
Steps 6 to 8 are the baby-step giant-step part. If this is replaced
by Pollard rho (doing all group arithmetic mod p mod q), it may only
find a spurious collision, i.e. two values collide mod q without
colliding as group elements. I think this is not much more likely
than a "real" collision, though, so just repeating the attack a few
times will work.
Thanks, BTW - that was a very interesting problem, and it's helped
to clarify my understanding of DSA and of square root attacks.
- --
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
iQEVAwUBOHZcPjkCAxeYt5gVAQEQiggAgIcPwHEXPItuM5qoFU++C1GEkksG6+6p
+y/sZ0J6EfzXIxEP5jEEGvpYhBRG9RXFj1l6+73I5BHGtflDAGEw9VkDfcTzXrL6
z8l4KpGsLdpXP4fwa8kMh9yytq2eck6PRyWHWTku0s8wngoqhJ9uQxKIa1Feo3/Q
A5OkzAYUGaW4NTMa/oiEZdg8WyagV/Mf8mjaM/A2rs3H+oC+qQxCaJxjD6DE28+9
X1Ezf1p6wlKPjxsAwpXP+QXuVR7zgmYaxKIucd9rqC28//noOxBMUe0QgK5qRjG1
Z89bgHUNwjWhwbVGt/icOO997UUspUFJLVMKgmdFyz9lP2MvCLqMwg==
=PJpO
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 07 Jan 2000 21:42:04 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Square?
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
>
> Tom St Denis wrote:
> >
> > All I know is in the paper 'The Block Cipher: Square' they have an
> > attack for anything under 6 rounds. I can send copies to anyone who
>
> It appears certain that any block cipher with sufficiently reduced
> number of rounds can be cracked. Hence the question: Why are block
> ciphers with (designed) variable, instead of constant, number of
> rounds not very common?
Square actually can have a variable number of rounds, as described in
section 7 of "The Block Cipher Square". The key schedule is capable of
generating any required number of subkeys.
> With that parametrization an algorithm could adapt to the future
> advances of analysis techniques at least to some reasonable extent
> and hence survive.
I agree.
- --
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
iQEVAwUBOHZdlDkCAxeYt5gVAQGkQgf9HWzIwaLsXNZSiIfQN+IBSSMcIK/tLpIC
0VrCZRD3pNznMBgurnkZ2OzmfNwIwGF15gp4ZbTtr47I0hlQmOC50nfOPrQe311D
42RvjaXQn4tkEoAhIIi5OyG1vISVwGX8NMw8KU+4qSuO4pzGE0nvyUSEf2faB3tg
VZS1oGpHtd0NqQM/nWzmF/tRhBmfo515opVDe5jQvAA72bznrv3hmQRwNKZjWLZP
kd2At3ufhdcUKzjkj64FsY7UtnwJxuwGJOjFhWC10iwdyVMHT6RDJgRgQT5P4z+W
MRQmEfAsLYcuL8NBfztImL3pFVd+Jn9yu31fifkRyLoHHn+hT3bI1Q==
=kTCb
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 07 Jan 2000 21:47:01 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Anonymous Source Problem
=====BEGIN PGP SIGNED MESSAGE=====
Hans wrote:
>
> I'm working with a problem which I believe can be solved using
> cryptographic methods. After scanning the books (Applied Cryptography
> and others) and the web, I've not been able find a solution. The
> problem involves protecting an individual's identity.
>
> Here is a description of the problem-
>
> Peggy has some information she wants to send Victor, who is
> a reporter for a newspaper. Peggy wants to remain anonymous.
> Since Victor is able to verify the information Peggy provided,
> he now trusts her even though he doesn't know her true identity.
I.e. Victor trusts the information in the messages sent to him
if-and-only-if he knows that they all come from the *same* source,
and that his communications with that source are confidential and
tamper-resistant. (Also note that this is true whether the source
is a single person, or more than one person sharing an identity.)
> Alice is also providing information anonymously to Carol, who similarly
> trusts Peggy. Peggy doesn't want Victor and Carol to know they are
> getting information from the same source.
>
> Victor and Carol, however, need a way of knowing with full confidence
> that information is coming from Peggy, and not an imposter posing as
> Peggy. Similarly, Peggy wants to be sure that she is talking to Victor
> (or Carol). Note that it is also in Peggy's interest that no one can
> impersonate her.
>
> A mutual authentication is needed- however, only one can know the true
> identity of the other.
>
> Everyone (Peggy, Victor, and Carol) has an ID certificate with their
> true identities which is signed by Trent, a CA trusted by everyone.
> The ID certificate has a unique value which identifies the individual.
> So, Peggy asks Victor for his certificate, and checks it with Trent's
> verifying signature.
>
> The problem is- how Peggy prove her (anonymous) identity to Victor?
>
> I'm hoping there is a way of Peggy can create a new 'anonymous'
> certificate based on Peggy's and Victor's (or Carol's) certificate.
> [...]
You're making this far too complicated. Here's a simpler approach:
Peggy generates two key pairs, one for use with Victor, and one for use
with Carol. (The number of key pairs is doubled if signature and
encryption algorithms use different keys; in that case encryption public
keys should be certified using the corresponding signature key, as in
OpenPGP, for example.)
Peggy also obtains Victor and Carol's public keys, certified to her
satisfaction. No certification of Peggy's public keys is necessary,
since all that Victor and Carol need to know is that they are receiving
a set of messages which all come from the same source, and have not been
tampered with (e.g. no attacker has cut-and-pasted text between messages,
or inserted new messages which purport to be from this source). It
is also not necessary for there to be any link between Peggy's key pair
which she uses for Victor, and her key pair which she uses for Carol.
Simply signing and public-key encrypting messages (using PGP, say),
is sufficient to achieve all of this, provided that Victor and Carol
check that the same public key can be used to verify each message.
To achieve anonymity, either a remailer network (e.g. MixMaster),
or a public medium (e.g. alt.anonymous.messages) can be used.
If a CA is involved then only Peggy needs to trust it (and only to
the extent that she is confident of having Victor and Carol's authentic
public keys); Victor and Carol do not.
- --
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
iQEVAwUBOHZeojkCAxeYt5gVAQGosQgAnAi19/uDr6K5DknZ0yftv2/0PQFzJzle
ROmUjaoEWafenxxClQ2EuGpfHDxYhJPLtFGKzAbeobp7N23/FKWSlKZd8Ylokg8u
12E+huv40zbOhtS+8rMnj5aPAWz0QDNYVQ5r3Ejoe7ISaHP1hDK+mBeETobjticI
YarGPSadRwGlQt72bcFJ4zD1d6J4Cida2B0ECxQKpb/owHgdfDMLFY9tJ3O5f0Nc
Pxt+hqBw5R5CMgFrs7MDYAHwPcOJkknVuwyyf6xUSK8oghjkyRk705Z84jSActgZ
nAol8HTMHeey/kpr/BW/AcFvLduY/Z5mFFrAUkdTzF0yiolIpWLiOg==
=HZwE
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 07 Jan 2000 21:48:17 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Anonymous Source Problem
=====BEGIN PGP SIGNED MESSAGE=====
Hans wrote:
[...]
> Your idea of generating key pairs is correct, except for my application
> there is no way for Peggy to store the private keys for every Victor.
OK, let Peggy's private key for communications with Victor be re-calculated
as H("Victor", secret), every time she needs to use it (where H is based on
a hash function, and 'secret' is all that Peggy needs to store, regardless
of the number of Victors).
I'd suggest using DL or ECDL-based signature and encryption algorithms,
where the parameters can be common to all users, and the private value
can be any bit string of sufficient length.
- --
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
iQEVAwUBOHZfCDkCAxeYt5gVAQHu7Qf8COcMVHqe8s7ZqCz0GfT0+eGlb1tjG96l
Dvl9BYTVGNGfk4tqJxKcG/l+ePpfuGlndrRlXIDPb9+xLWwopXajsNx0xeTqISxk
68m4SvjSiiJCpfKXmjmEGSb2YtzTjrQSfAIY4Fk+zqqh3NqdArGQ+LoL1S96FXsc
53VzOud+/zSWIKgLGldURXI+1QefAdZlwArFFvqFcNNj90Cp0j9QtBTZ9ZZZzVPL
fSU1gbrRoVR1QuipFA3fuwBj1wWbolgfQMwxEX3g6Z6OeGJCu+90fXnz5YYgaolA
P9FlLZ/eFf6uoReoK3AlZXamx42BK1+KLp9ihYpgOcMHcl37p+gY5w==
=pY7q
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Steve K)
Subject: Re: Unsafe Advice in Cryptonomicon
Date: Fri, 07 Jan 2000 22:49:13 GMT
On Fri, 07 Jan 2000 20:53:43 GMT, [EMAIL PROTECTED] (Steve K) wrote:
come to think of it, it would all be buzz. haven't played with motors
in ages...
Steve K
---Continuing freedom of speech brought to you by---
http://www.eff.org/ http://www.epic.org/
http://www.cdt.org/
PGP key 0x5D016218
All others have been revoked.
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Wagner et Al.
Date: Fri, 07 Jan 2000 17:19:16 -0600
In article <[EMAIL PROTECTED]>, "John E. Kuslich"
<[EMAIL PROTECTED]> wrote:
> There is very little software can do to protect itself from anyone who
> can gain access to your computer either by physical means or by the
> network through BackOrfice and similar trojans.
>
> Resistance is futile...at least as far as crypto software on the PC is
> concerned.
>
There are other optionsfor security, just not popular ones. Hardware
solutions are in order, as a software reality is eternally not tamper
resistent in itself.
--
To prevent the comprimise of with the most common configuration
of computers is something like preventing a sculptor from being too original. If a
computer design is corruptable, it will be.
------------------------------
From: [EMAIL PROTECTED] (Dan Day)
Subject: Re: How to pronounce "Vigenere"?
Date: Fri, 07 Jan 2000 22:54:51 GMT
On 06 Jan 2000 23:03:39 EST, [EMAIL PROTECTED] (Guy Macon) wrote:
>
>VIY-AAH-GRUH???
And how much is Pfizer paying you for that plug? :-)
--
"How strangely will the Tools of a Tyrant pervert the
plain Meaning of Words!"
--Samuel Adams (1722-1803), letter to John Pitts, January 21, 1776
------------------------------
** 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
******************************
