Cryptography-Digest Digest #946, Volume #10 Fri, 21 Jan 00 09:13:01 EST
Contents:
Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?) (Richard Herring)
Re: Intel 810 chipset Random Number Generator (Guy Macon)
Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?) (Guy Macon)
Re: Forward secrecy for public key encryption: MYH (David Hopwood)
Corrections to MYH (David Hopwood)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Richard Herring)
Subject: Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?)
Date: 21 Jan 2000 11:49:27 GMT
Reply-To: [EMAIL PROTECTED]
In article <865oml$[EMAIL PROTECTED]>, Guy Macon ([EMAIL PROTECTED])
wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Douglas A. Gwyn) wrote:
> >
> >Paul Gover wrote:
> >> I was told by a foreign friend that the normal rule for English is that
> >> the emphasis is on the third syllable of the word. Hence the normal
> >> pronunciation of omnipotent. It's always amused me how much better
> >> foreigners' understanding of English is than native speakers'.
You snipped DAG's telling comment.
> No rule is perfect, but "next to the last syllable" comes much
> closer than what your foreign friend came up with.
As a native speaker of British English, personally I put the stress
on the *second* syllable. So does my dictionary.
--
Richard Herring | <[EMAIL PROTECTED]>
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Crossposted-To: sci.physics
Subject: Re: Intel 810 chipset Random Number Generator
Date: 21 Jan 2000 07:21:27 EST
In article <868fep$67s$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Michael
Kagalenko) wrote:
> That's fair comment, however note, that quartz crystals are a very common
> component of digital equipment, and atomic time standard is available
> via internet. You can produce thermally random
> data by measuring the clock drift against more precise clock (first
> you'd have to find out the crystal frequency, of course). To elaborate
> a bit, if t is precise time, and t' is the time measured by quartz
> oscillator (reclaibrated by using t to avoid systematic drift),
> then
> <t-t'> = 0 (1)
>
>(<> stands for math. expectation), however, that does not
> mean that there is no drift, but that drift in both directions is equiprobable
> (the recalibration I mentioned above consists in making sure that (1)
> holds)
>
> If the drift can be assumed to be brownian random walk,
> the average square drift < (t-t')^2 > grows linearly with time
>
> < (t-t')^2 > = constant * t
The nature of crystal oscillators is to have a random variation
in frequency that varies around the center frequency in a 1/F
fashion, plus a long term drift in one direction as the crystal
ages. In addition, you vave to decide when the waveform goes
from 0 to 1 or from 1 to 0. To do this, you have to measure
the voltage of a signal with a finite risetime, which means that
elecrical noise has an effect on how much jitter you see.
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Mispronounce words. (OT Re: How to pronounce "Vigenere"?)
Date: 21 Jan 2000 07:35:14 EST
In article <869h47$8it$[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Richard Herring)
wrote:
>
>> No rule is perfect, but "next to the last syllable" comes much
>> closer than what your foreign friend came up with.
>
>As a native speaker of British English, personally I put the stress
>on the *second* syllable. So does my dictionary.
>
Interesting! I am a Los Angeles California native, and we get
to be the standard for "accent free" American English because
all of the movies and television shows are made here. ;)
Clearly, for one or three syllable words both rules act the same.
For two syllable words and four or more syllable words the rules
diverge. Do you really say britISH instead of BRITish, highLAND
instead of HIGHland? InSTALLtion instead of InstaLAtion, and
therMOnuclear instead of thermoNUclear?
Of course there are always exceptions, such a MICrosoft and
InterPLANetary...
------------------------------
Date: Fri, 21 Jan 2000 10:42:26 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Forward secrecy for public key encryption: MYH
=====BEGIN PGP SIGNED MESSAGE=====
David Wagner wrote:
>
> Ahh, I see, that didn't work. I didn't read far enough....
>
> Ok, let's try again. We have
> y_t^h = F(R,t)^{2 s h} = y^{2 s x_t} mod m
> where y_t,h,R,t,y,m are public, s is secret, and x_t may be assumed
> to be available to the adversary in an attack against the forward
> secrecy. Yes?
Yes.
> (The right-hand side follows because y_t^h = alpha^{2 s x_t log(y)}.)
Yes.
> Now I want to play the same games as before. Let a = F(R,t)^h mod m and
> b = y^x_t mod m, and notice that
> (a^2)^s = (b^2)^s mod m.
a = F(R,t)^h
= F(R,t)^(2.s.u.log_alpha(y))
= y_t^(u.log_alpha(y))
= alpha^(log_alpha(y_t).u.log_alpha(y))
= alpha^(log_alpha(y).u.log_alpha(y_t))
= y^(u.log_alpha(y_t))
= y^x_t
= b
I think that answers your question :-)
[Incidentally, in Maurer's original scheme, this is closely
analogous to:
Let a = ID_A^(2.u.log(ID_B^2)) mod m
b = ID_B^(2.u.log(ID_A^2)) mod m
where a = b = the Diffie-Hellman result. In your attempted attack,
a = b = the DH result when k is chosen to be 1.]
> [...] (For example, for all I know, maybe the definitions ensure
> that a = +/-b always holds, and then of course the "attack" won't
> work.)
Exactly. Another nice try, though.
- --
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
iQEVAwUBOIg22zkCAxeYt5gVAQES+AgAzPILnktonmPFNMcUeFQBio/bTQ/oD1V6
9YjBHmn5jM+H8mDdXUO10RzfiwgGmfYjnjGKm3r62ogLowc7yP/3YSeAqEc4eed1
zeFB39wI09N6Ehz+seSHo6SNiZ+gKgXygPr9l6oAv6qmKrMTVDfLC2NM27zVZRK8
McGfSaZFeucGF4wOfN4JwksZeXHjTuqovH7B9M0YcxmBYFml6Vw4hQrgLYneJU+U
9l9rRVKB5ks0CpTv4HmdxMXlUpuDqU8SZv1s8aO09WvMpYMK0KdHnBGjH8AMbDHI
fC3m8JojOtxF5p4YYIfTYu50evepBXunewFNt1zaZCd/kvAZ477lqw==
=v1mJ
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 21 Jan 2000 13:31:31 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Corrections to MYH
=====BEGIN PGP SIGNED MESSAGE=====
Hal Finney (in private email), and also someone posting via the lcs
Mixmaster Remailer, have pointed out some errors; for the algorithm
as described, the alpha_i will not in general have order q_i in Z*_m
(as opposed to Z_{p_i}).
The order of g is also not phi(m), it is
ord(g) = lcm[p_i - 1: i = 1..r] = phi(m)/2^(r-1)
Another problem is that y and h are dependent on F(H(m, y, h, l_k), 0),
i.e. a hash of themselves, which is not implementable.
Below is a version that corrects these errors, and makes the
following additional changes:
- The size of public and private keys is decreased: the public
key can be stored in a "compressed" form which is about a third
smaller than before, and each of the private exponents is now
only the same size as q, rather than m.
- Making the private exponents smaller also makes decryption
faster. (This does not affect security because we were
operating in the subgroup anyway, so the exponent is
effectively reduced mod q.)
- A check has been added during key pair generation that none
of the y_t are "weak", in the sense of generating a subgroup
of order less than q. The probability of this happening should
be very small (bounded above by T * r / min[q_i: i = 1..r]),
but it is easy to check for.
- An encoding of the algorithms used (which could be simply a
string of the form "MYH(H,F,SYM,MAC,eLen,mLen)", for example)
is added to the input of the hashes used for public key
calculation, and encryption/decryption. This prevents an attack
on the agreement between sender and recipient of the precise
variant of MYH to be used. For example, the attacker could
convince the sender and recipient to use different encryption
algorithms; because the MAC is on the ciphertext rather than
the plaintext, this would not be detected, which would be a
break of the non-malleability property. In the new version,
any attack of this kind would result in BAD being output from
the decryption algorithm.
========
Definitions and Notes are as before, except for:
> Let F be a pseudo random function that maps a bit string to the
> set of integers [2, m-2]. (This could for example be based on
> MGF1 from [P1363].)
Change this to
Let F[a, b] be a pseudo random function that maps a bit string
to the set of integers [a, b], without significant bias. (This
could for example be based on MGF1 from [P1363].)
Add a note that unless otherwise specified, exponentiation is mod m,
and multiplication of exponents (i.e. in the right hand side, or
"superscript" of an exponentiation expression) is mod ord(g).
> Key pair generation [full version]:
>
> 1. Choose distinct random primes p_1..p_r, of roughly equal size
> and where the factorisations of p_i - 1 are known, such that
> the values (p_i - 1)/2 are odd and pairwise relatively prime,
> and q_i is a prime dividing (p_i - 1)/2 for each i.
>
> Let m = product[p_i: i = 1..r]
> q = product[q_i: i = 1..r]
> z_i = (p_i - 1)/q_i
To correct the bug pointed out by Hal Finney et al, this should be
changed to
z_i = ord(g)/q_i
where ord(g) = lcm[p_i - 1: i = 1..r].
> s = sum[z_i: i = 1..r]
>
> The q_i (which are necessarily all distinct) should be primes of
> a size such that Pollard rho is practical in a subgroup of size
> q_i for each i, but not in a subgroup of size q. A reasonable
> choice for this size would be 40 to 60 bits.
> The z_i must not be smooth, and should preferably each be twice
> a prime number.
This last sentence should be changed to:
The values (p_i - 1)/q_i for each i must not be smooth, and
should preferably each be twice a prime number.
(i.e. the same meaning as before).
> 2. Select elements alpha_i that generate subgroups of sizes q_i, as
> follows:
>
> a) Choose an element g of Z*_m that is primitive in each of the
> prime fields Z_{p_i}, i.e., such that for i = 1..r, p_i - 1
> is the smallest exponent for which g^(p_i - 1) = 1 (mod p_i).
>
> (To test whether g is primitive in Z_{p_i}, check that
> g^((p_i - 1)/a) mod p_i != 1 for each prime factor a of
> p_i - 1.)
>
> b) Compute alpha_i = g^z_i for i = 1..r.
> alpha = product[alpha_i: i = 1..r].
>
> [Note that:
> - g has maximal order phi(m) in Z*_m,
Change to
- g has maximal order lcm[p_i - 1: i = 1..r] in Z*_m,
> - alpha_i has order q_i,
^ in Z*_m.
> - alpha has order lcm[q_i: i = 1..r] = product[q_i: i = 1..r] = q,
With the new definition of z_i, this is now correct, but it could be
read as implying that *in general*, the order of any product of elements
with orders q_i, is always the LCM of the q_i, which is not true.
However, it is always the case that given the definitions above,
alpha has order q.
[Proof:
alpha^q = product[alpha_i^q: i = 1..r]
= product[g^(ord(g).q/q_i): i = 1..r]
= 1
so the order of alpha in Z*_m divides q. It will be exactly q iff for
i = 1..r, alpha^z_i != 1 (mod m) (since z_i = ord(g)/q_i).
alpha^z_i = (g^sum[z_j: j = 1..r])^z_i
= g^sum[z_i.z_j: j = 1..r]
= g^sum[(ord(g)^2)/(q_i.q_j): j = 1..r] [*]
but (ord(g)^2)/(q_i.q_j) is a multiple of ord(g) for i != j (the q_i
are all distinct, so q_i will cancel with a different factor of ord(g)
than q_j; each factor of ord(g) will appear either once or twice in the
resulting product). Therefore the terms of the sum for which i != j
are all zero (modulo ord(g)), which implies that
alpha^z_i = g^((ord(g)/q_i)^2) [*]
= g^(z_i^2) [*]
= (g^z_i)^z_i
Since g^z_i has order q_i, and since z_i is not a multiple of q_i,
it follows that alpha^z_i != 1 (mod m) for i = 1..r, and therefore
alpha has order q.
[*] The expressions for the exponents in these lines should be
interpreted as integer (rather than modular) arithmetic.]
> - alpha = g^sum[z_i: i = 1..r] = g^s.]
>
> Let R be a hash of the public key - see later for the precise
> definition. (R will be used as a random seed for the generation
> of public values; a hash of the public key is a convenient way
> of doing this that does not require extra data to be stored,
> and has some security advantages.)
This tries to calculate H(m, y, h, l_k) before y, h, and l_k
are known. Also, y_0 = y is calculated as F(R, 0)^s, creating a
cyclic dependency.
The fix for this suggested below also allows a public key to be
"compressed", so that y does not need to be stored.
Let 'MAKE_y' and 'MAKE_y_t' be distinct tags, used as input to
F, to indicate that independent outputs are to be produced.
Let beta = F[2, m-2](MAKE_y, m, l_k)^2,
y = beta^s.
If y does not have order q in Z*_m, start again with a
different m.
Calculate the discrete logarithm w = log_alpha(y), using
the same method as in step 3 below.
Choose u at random from [1, q-1].
Let h = 2.s.u.w mod phi(m).
Let VARIANT be an encoding of the variant of MYH that is being
used (including an unambiguous specification of F, H, SYM, MAC,
eLen, and mLen).
Let l_k = floor(log_2(q)) + b,
R = H(VARIANT, m, y, h, l_k).
where b is a security parameter (a reasonable value for b would
probably be about 40).
Add the following check that none of the y_t will be "weak":
For t = 1..T (where T is the number of time periods),
If F(R, t)^(2.s) does not have order q in Z*_m, start key
pair generation again with a different m.
> 3. For t = 0..T (where T is the number of time periods),
Change this to 1..T (0 was the index for the "dummy" public/private
key, which is now calculated above).
> a) Let beta = F(R, t)^2,
> y_t = beta^s.
>
> b) Calculate the discrete logarithm w = log_alpha(y_t).
> Note that since y_t = beta^s, alpha = g^s, and alpha_i = g^z_i,
>
> log_alpha(y_t) = log_g(beta) (mod q)
> = log_alpha_i(beta^z_i) (mod q_i)
>
> [beta^z_i is guaranteed to be in the subgroup of order q_i
> generated by alpha_i.]
> Therefore we can calculate w as follows:
>
> i) For each i = 1..r, use Pollard rho (see Algorithm 3.60 of
> [HAC], or [Pollard]) to compute the discrete log w_i of
> beta^z_i mod p_i to the base alpha_i.
^^^^^^^ should be mod m
>
> ii) Solve the system of congruences
>
> w = w_1 (mod q_1 - 1)
> : : :
> w = w_r (mod q_r - 1)
>
> by the Chinese remainder technique (e.g. Algorithm 14.71
> of [HAC]). Note that w will be in the range [0, q-1].
>
> c) Let x_t = u.w mod phi(m).
Change to
c) Let x_t = u.w mod q.
Delete the following part, because it has already been done:
<<<<<<
> 4. Let y = y_0,
> h = 2.s.x_0 mod phi(m),
> l_k = floor(log_2(q)) + b.
> Let R be a hash of the public key [...]
>>>>>>
> Retain (m, h, y, l_k) as the public key, (x_1..x_T) as the
> private key, and delete all other values (p_i, q_i, q, z_i,
> s, g, alpha_i, alpha, x_0, u, and any intermediate results).
Change this to
Retain (m, y, h, l_k) as the public key (this may also be stored
in a "compressed" representation, (m, h, l_k)).
Retain (R, x_1..x_T) as the private key, and delete all other
values (p_i, q_i, q, z_i, s, g, alpha_i, alpha, x_0, u, and
any intermediate results).
[...]
> Encryption [full version]:
>
> 1. Obtain the recipient's authentic public key (m, y, h, l_k), and
> the current time period t (or a time period in the near future,
> to take into account delays in delivering a message).
> Let M be the plaintext message.
Change to:
1. Obtain the recipient's authentic public key, either in the
"compressed" form (m, h, l_k), or as (m, y, h, l_k).
If the former, calculate
y = F[2, m-2](MAKE_y, m, l_k)^(2.s).
An uncompressed key with a value for y that is not consistent
with the above definition, may be treated as invalid.
> 2. Choose a random k in [1, 2^l_k - 1].
>
> [This differs from [DHAES], ...]
>
> 3. Calculate R = H(m, y, h, l_k),
> X = (F(R, t)^h)^k,
> U = y^k,
> hash = H(U, X),
Change to:
3. Let VARIANT be an encoding of the variant of MYH that is being
used, as in step 2 of key pair generation.
Calculate R = H(VARIANT, m, y, h, l_k),
X = (F[2, m-2](R, t)^h)^k,
U = y^k,
hash = H(R, U, X),
It is intentional that hash depends on R both directly, and indirectly
via X.
> macKey = first mLen bits of hash,
> encKey = next eLen bits of hash after macKey,
> encM = SYM.enc(encKey, M),
> tag = MAC.gen(macKey, encM),
>
> The ciphertext is (t || U || tag || encM).
>
> [Note: The pseudocode for encryption in figure 2 of [DHAES]
> is incorrect; it applies the MAC to M, whereas the rest of
> the paper, including the security proofs, applies it to encM
> as shown here.]
>
> Decryption [full version]:
>
> Note that an output of BAD means that the ciphertext was not valid.
>
> 1. Parse the ciphertext as (t || U || tag || encM)
> (if it cannot be parsed this way, or if t = 0, output BAD).
>
> 2. Calculate X = U^x_t,
> hash = H(U, X),
Change to:
hash = H(R, U, X),
(note that R is part of the private key).
> macKey = first mLen bits of hash,
> encKey = next eLen bits of hash after macKey.
>
> If MAC.ver(macKey, encM, tag) fails, delete any intermediate
> results, and output BAD.
> Otherwise, the plaintext is SYM.dec(encKey, encM).
[References are as before.]
- --
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
iQEVAwUBOIhfYTkCAxeYt5gVAQHPzwgAkU4PLXNswbQj4g4yhTWV3JAHZuKxeXHF
c5dgcrn+D4pljoVfisRaK7j7YFDQVM9BsG1dl2eg1eSauEWaVrRY1nZ1BIljgips
s0DwboubvytW4k5yqrdEVsdHgvcEHw+MWC/zdzFk0w6Az/P+XuNw8yZFgh/OD8y+
LLPSlPq1ENh8sS4Yn3HifImIMglSaKcXJs7zxCmh+rrRD4HwBpjBxGp4J+Y5u1sF
xuIiidkB12czo0/B6uCEm92PJbduHXxgHaJwejHZ4cmYgxhMJfsVBV2w7xDb1FUU
018OlODT+362A5T0Z4vhGf3hj4br5USYm/Rn/CW/oS5JViYBE0CTtQ==
=lcrG
=====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
******************************
