Cryptography-Digest Digest #108, Volume #11 Sat, 12 Feb 00 17:13:01 EST
Contents:
Re: *** ECC - new strong and fast calc method ("Craig Clapp")
Re: RFC: Reconstruction of XORd data (David A Molnar)
Re: BASIC Crypto Question (Johnny Bravo)
Has some already created a DATA DIODE? (No Spam)
----------------------------------------------------------------------------
From: "Craig Clapp" <[EMAIL PROTECTED]>
Subject: Re: *** ECC - new strong and fast calc method
Date: Sat, 12 Feb 2000 20:51:26 GMT
David Hopwood wrote in message <[EMAIL PROTECTED]>...
>-----BEGIN PGP SIGNED MESSAGE-----
>
>Greg wrote:
>>
>> Here is another stab at trying to make things run faster for ECC.
>> Assuming that none or only portions may already be covered by
>> existing patents, the remainder is immediately submitted to the
>> public domain for free use by all.
>>
>> Patents that MAY have some overlap include 5,987,131.
>>
>> Given a curve over a field of say 163 bits, I have found
>> that average performance in calculating a point multiplication
>> can be reduced to 1/3 the time if all points resulting from
>> each power of 2 are precomputed and the ones matching the powers
>> of two in the private key are then added together.
>
>This is a special case of a well-known technique called "fixed
>base windowing", for example see Handbook of Applied Cryptography
>section 14.6.3 (which describes it for exponentiation in a
>multiplicative group, but it's obvious that it also applies to
>multiplication in an additive group). The algorithm you've described
>is the case where h = 2.
>
>Chapter 14 of HAC is at
>http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf (or .ps);
>I strongly recommend reading it. Chapter 3 is also relevant to
>this thread.
>
I second that recommendation.
>
>> This is the part that most likely conflicts with 5,987,131.
>
If you have enough storage space for 163 powers of the base
(including the base itself), then you would need just 28 point
additions to achieve 160-bit exponent diversity by properly
applying the techniques of US5,987,131, not the 80 that you
plan on doing. If you use the fixed-base comb method of [LL94]
(see also HAC 14.6.3 (iii) ) then you can get by with 36 point
additions. To get down to 28 point additions using the fixed-base
comb method you need something north of 381 table entries
(381 is enough to get down to 29 point additions, 508 gets you
down to 27).
>
>Fixed base windowing is not patented.
Hmmm. If you are using the term as it is used in HAC (which for
all I know may be the origin of this term), then you may note that
HAC attributes the fixed-base windowing method (algorithm
14.109) to Brickell et al. (HAC page 633, ref [204] ). This is
the method embodied in U.S. patent 5,299,262 (HAC ref [203] ).
Moreover, this is one of the ten selected patents that HAC
details in section 15.2.3, and HAC page 644 explicitly references
the technique of US5,299,262 as that presented in algorithm 14.109.
Of course, the scope of the patent is defined by its claims, all of
which are related to using the fixed-base windowing technique for
exponentiating in cryptographic systems. So, strictly speaking you
may be right - fixed base windowing is not patented in the abstract
sense. If you have non-cryptographic uses for the fixed-base
windowing technique then you'll probably have no problems with
patent infringement. :-)
> In fact, mathematical
>algorithms are not supposed to be patentable (in any country,
>AFAIK), although the US Patent Office in particular is very
>inconsistent about applying this rule.
>
>[...]
>> Additionally, if the key space is limited to 80 bits (in this
>> case), the number of point additions on average is cut in half.
>> That is, the average time it takes to calculate the resulting
>> point is 1/6 of the average using standard calculations using
>> a full key space. I argue that security is not weakened for
>> the following reasons:
>>
>> Some have argued that 80 bits is enough to prevent a brute force
>> key search attack. This is accepted as obvious.
>>
>> Some have argued that limiting the private key to 80 bits is enough
>> to make the Pollard Lambda (aka Pollard Kangaroo) attack feasible,
>> since the attack can be limited by boundaries in the key space.
>>
>> However, if the bits that are used to define the key are 80 in
>> number, it does not matter where they are located. The total
>> time to calculate remains roughly the same. Therefore, they
>> can span the entire 163 bits in any random fashion.
>
>The sci.crypt thread from November 1999 (title "bits of
>diffiehellman private key") that I mentioned before was about
>precisely this case, assuming the positions of the 80 bits are
>known but arbitrary. In this case the cost of the attack described
>there would be 2^41 curve additions (with a fairly large memory
>requirement of 2^40 curve points, although it may be possible to
>reduce that).
>
>Also note that as pointed out in the notes on page 128 of HAC, an
>exponent space with a Hamming weight of t (i.e. there are exactly
>t set bits but in unknown positions), can be searched in
>k * (k/2 choose t/2) steps (where k in this case is the number
>of bits in the largest factor of the group order, if the attack
>is combined with the Pohlig-Hellman discrete-log algorithm).
>
The following discussion is excerpted from an unpublished paper
relating to the invention in US5,987,131, addressing the security
of low Hamming weight exponents whose positions are
unconstrained. It draws heavily on the work of VanOorschot
and Wiener.
=========
4.2 Exponent diversity to foil meet-in-the middle attacks
A standard method of direct attack against short exponents
is a meet-in-the-middle attack. Such attacks have complexity
that is approximately exponential in half the length of the
exponent, i.e. on the order of the square-root of the number
of possible values that the exponent can take. While the
simplest such techniques also require an amount of storage
of similar order, which is generally impractical, the best
techniques can approach this computational bound even with
comparatively modest amounts of memory [OW94, OW96a].
Heiman showed that low Hamming weight exponents are also
susceptible to a meet-in-the-middle attack, though in this
case having somewhat greater than square-root complexity
[Hei92]. VanOorschot and Wiener in [OW96a] improve on Heiman’s
result, bringing such an attack closer to the square-root bound.
They show that for the case of exponents of even length u bits
and having known even Hamming weight w, there exists a meet-in-the-
middle attack needing on average (u pick w)/((u/2 pick w/2)^2)
trials each of complexity (u/2 pick w/2), thus giving an expected
work factor of (u pick w)/(u/2 pick w/2). The number of possible
keys of length u and with Hamming weight w is (u pick w) and
prudent design would anticipate an attack of square-root
complexity. For usefully large keyspaces the work factor of
vanOorschot and Wiener’s attack can be shown to be no less
than the square root of the number of possible keys. Using
Stirling’s approximation:
Attack_complexity / square_root_of_keyspace
= sqrt((u pick w))/(u/2 pick w/2)
~= (pi*w(1-w/u)/2)^(1/4)
which is greater than 1 if u>2 and w!=0. In [OW96a] the
attack is described for the case of u and w even. If either
of u or w is odd then the attack can still be performed but
at marginally reduced efficiency.
=========
>
>Suppose, for example, that we are using a curve of prime order
>over GF(p) with p a 180-bit prime, and exponents with a Hamming
>weight of 46 (i.e. just over half as many bits set as normal);
>then
>
> 180 * (90 choose 23) = 180 * 90! / ((90-23)! * 23!)
> = 2^(log2(180) + sum[log2((91-t)/t): t = 1..23])
> =~ 2^76.9
>
>(This is an upper bound on the security level, better attacks
>are not ruled out.)
Indeed. Using (180 pick 46)/(180/2 pick 46/2) from the previous
discussion shows the security level to be no better than 2^73.3
>The field size for equivalent security with
>full length exponents is 154 bits, which at first sight looks
>slightly less efficient (since the time for a curve multiplication
>using fixed-base windowing with h = 2 is proportional to the
>square of the field size multiplied by the Hamming weight of the
>exponent, and 180^2 * 46 is about 18% less than 154^2 * 77).
>However, any performance advantage for the low-Hamming-weight
>approach goes away when you consider fixed-base windowing with
>h > 2, or other multiplication/exponentiation algorithms (for
>example Lam and Hui's string-replacement algorithm mentioned at
>the end of the notes for Chapter 14 in HAC).
>
>
>Bottom line: don't use short exponents or exponents with a lower
>than expected Hamming weight for ECC, because it doesn't improve
>the security/speed trade-off.
>
I have studied [much of] the literature on exponentiation of a fixed
base, and am unable to share your conclusion. The exponentiation
method used in US5,987,131 appears to achieve the desired key
diversity with fewer modular multiplications (/point additions)
and/or fewer table entries than exponentiation using methods
applicable to arbitrary exponents, such as [BGMW92/BGM94],
[LL94], and [Roo94]. I haven't studied the string replacement
methods at length, but my reading of HAC leaves me believing that
they are less efficient than the other methods I referenced since
they appear not eliminate squarings (/point doublings).
US5,987,131 uses low-Hamming weight exponents to achieve a
160-bit exponent diversity with, for instance, exactly 50 modular
multiplications when using a fixed table of just 20 entries and
a single accumulator. The methods of [BGMW92/BGM94], [LL94],
and [Roo94] need tables of 45, ~45 and 32 entries respectively to
achieve 160-bit exponent diversity with, _on average_, as few as 50
modular multiplications. Moreover, [Roo94] needs read/write
table space rather than read-only. For all of these other methods the
table size becomes even bigger in order to achieve a worst-case time
(or fixed-case time) of 50 multiplications.
Other examples for a key having 160-bit diversity using the method
of US5,987,131 are:
30 modular multiplications and a fixed table of 120 entries
40 modular multiplications and a fixed table of 40 entries
50 modular multiplications and a fixed table of 20 entries
60 modular multiplications and a fixed table of 12 entries
80 modular multiplications and a fixed table of 6 entries
where the number of modular multiplications is constant for all keys,
and in each case the only other storage required is the working
accumulator.
An interesting question is how many modular multiplications does
it take to achieve 160-bit key diversity if the only resources
available are a single table entry, i.e. the base itself (read-only), and
a single working register? Conventional wisdom might suggest
that you can't do better than the simple left-to-right binary method.
This uses (on average) 239 modular multiplications (of which
160 are squarings). Well, US5,987,131 shows how to do it with
just 230 modular multiplications _worst case_, of which at least
165 are squarings. Worth studying IMHO.
>
>> The randomness of the key bits' locations should effectively
>> make the Pollard Lambda attack useless against this key
>> space limitation, [...]
>
>There's a difference between making a conjecture that something
>is secure, and stating that it "should" be secure. You didn't
>have enough evidence for the latter.
>
>- --
>David Hopwood <[EMAIL PROTECTED]>
>
- Craig Clapp
[BGMW92] E. Brickell, D. Gordon, K. McCurley, D. Wilson, "Fast
Exponentiation with Precomputation", Eurocrypt ’92, LNCS 658,
Springer-Verlag, 1993, pp.200-207
[BGM94] E.F. Brickell, D.M. Gordon, and K.S. McCurley, "Method for
exponentiating in cryptographic systems", U.S. patent 5,299,262, Mar.29
1994, filed Aug.13 1992
[Hei92] R. Heiman, "A note on Discrete Logarithms with Special Structure",
Eurocrypt ’92, LNCS 658, Springer-Verlag, 1993, pp.454-457
[LL94] C.H. Lim, P.J. Lee, "More Flexible Exponentiation with
Precomputation", Crypto ’94, LNCS 839, Springer-Verlag, 1994, pp.95-107
[OW94] P.C. vanOorschot, M.J. Wiener, "Parallel Collision Search with
Applications to Hash Functions and Discrete Logarithms", 2nd ACM Conference
on Computer and Communications Security, ACM Press, 1994, pp.210-218
[OW96] P.C. vanOorschot, M.J. Wiener, "On Diffie-Hellman Key Agreement with
Short Exponents", Eurocrypt ’96, LNCS 1070, Springer-Verlag, 1996,
pp.332-343
[OW96a] P.C. vanOorschot, M.J. Wiener, "Improving Implementable
Meet-in-the-Middle Attacks by Orders of Magnitude", Crypto ’96, LNCS 1109,
Springer-Verlag, 1996, pp.229-236
[Roo94] P. deRooij, "Efficient Exponentiation using Precomputation and
Vector Addition Chains", Eurocrypt ’94, LNCS 950, Springer-Verlag, 1995,
pp.389-399
[Yac90] Y. Yacobi "Discrete-log with Compressible Exponents", ", Crypto ’90,
LNCS 537, Springer-Verlag, 1991, pp.639-643
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: RFC: Reconstruction of XORd data
Date: 12 Feb 2000 20:57:24 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
> Rick Braddam <[EMAIL PROTECTED]> wrote:
> : can be used to hold bits shifted out of a source register(src1, src2),
> : and supply bits shifted into a destination register (dest1, dest2).
> I'd have thought that readability and comprehensibility are important to
> anyone evaluating an algorithm. x86 assembler is a curious choice in
> these terms, IMO.
C doesn't have a nice way to express carry bits. If you're trying to
describe an algorithm which uses carry bits to acheive some kind of
optimization, assembler seems perfectly appropriate to me. At least
as long as the assembly is prefaced with a clear description of what
is supposed to be going on, as it was in this case.
Another example : the ARM family of processors is odd in that every
instruction is conditional. By that I mean you can add a suffix to
each instruction which tells it to execute or not execute based on
the contents of a condition register. This makes some suprising
optimizations possible.
The best way to talk about these optimizations is in ARM assembly
itself. While you can use some kind of pseudocode or english to
explain them, it just gets in the way.
Thanks,
-David
------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: BASIC Crypto Question
Date: Sat, 12 Feb 2000 16:20:05 +0000
On Sat, 12 Feb 2000 12:44:13 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
wrote:
>Johnny Bravo wrote:
>> Technically, the norm is to work on a multiple of 8 bits at a time, i.e.
>> "bytes" as most languages can easily read byte sized units from a file.
>> Another norm is working on multiples of 8 bytes, though there is no real
>> requirement for this (recent 128 and 256 bit block ciphers). Stream
>> ciphers of course work on a single byte at a time.
>
>No; while most computers store information in octets, ciphers
>typically operate on a bit stream or on blocks much larger than
>8 bits.
You missed the term "multiple" in that first line. :)
The blocks are usually multiples of 8 bits, RC4-1 byte, DES-7 bytes,
IDEA-16 bytes, Blowfish-32 bytes ect., while there are exceptions it seems
an easier way to deal with the octet that computers use to store
information.
Best Wishes,
Johnny Bravo
------------------------------
From: No Spam <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Has some already created a DATA DIODE?
Date: Sat, 12 Feb 2000 21:39:25 GMT
I thinking about the problems of using a PRNG for encryption, the
following seems clear.. to attack PRNG encryption you have you
have two options (assuming some of the plain data is known or
knowable (ie. it's english!).
First a brute force attack can be applied to the encryption key
(the seed) or secondly, knowing the plain data, the attacker can
work back to learn the state of the PRNG.
It is this second method of attack I would like the group's
comments on. Is there an (easy, quick, simple) way to create
what I call a DATA DIODE. A piece of code that is a one way
check valve, allowing the data to flow from a PRNG but does not
allow the attacker to back up the data path?
The following illustrates what I an talking about..
============================================================
+----+ +------------------+ +------------------+
|PRNG|--->| 15 bit integer A |-- + --| 16 bit integer B |
+----+ +-----------------=+ +------------------+
Then
+----------------------+ +---------------------+
| high 8 bit byte of B |-- + --| low 8 bit byte of B |
+----------------------+ +---------------------+
+-----+
Equals the 8 bit output encryption PAD byte | PAD |
+-----+
written in C:
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
int main(void)
{
unsigned char PAD[1];
int i,rand_num;
union diode {
unsigned int INT_B;
unsigned char byte[2];
} out;
out.INT_B = 1731;
printf("\nThe pad byte generation:\
\nINT A,\t\tINT B,\t\tINT B(HEX),\tPAD (HEX) ");
for(i = 0; i < 4; i++) {
rand_num = rand();
out.INT_B += rand_num ;
printf("\n %d,\t\t%d,\t\t%X, ", rand_num, out.INT_B, out.INT_B);
PAD[0] = (out.byte[0] + out.byte[1]);
printf("\t\t%2.X", PAD[0]);
}
return 0;
}
==========================================================
As an example, I use the first 4 integers output from the PRNG in
Borland's C, seeded with the number 1, which are:
346, 130, 10982, 1090..
we will set the starting state of integer B is 1731. So:
INT A + INT B0 int B1 <HEX> then INT B HI byte + LO byte = PAD
346 1731 2077 081D 08 1D 25
130 2077 2207 089F 08 9F A7
10982 2769 13189 3385 33 85 B8
1090 3807 14279 37C7 37 C7 FE
This system has two unknowns, the seed state of th PRNG and the
initial value of INT A.
My question how does the attacker proceed to learn the state of
the PRNG so as to determine the next PAD byte.
In this example there are 256 choices for each INT B..
for PAD 25 A7 B8
0025 00A7 00B8
0124 01A6 01B7
0223 02A5 02B6
0324 03A4 03B5
.... .... ....
2302 A502 B602
2401 A601 B701
2500 A700 B800
.... .... ....
FF26 FFA8 FFB9
The attacker would know that raw output of the PRNG can be seen
as the difference value between INT B and the preceding INT B.
However subtracting INT B(0) which has 256 possible values
from INT B(1) which also has 256 possible values yields 256 ^2
or 65536 possible answers.
I hope the group will not state that the attack answer is some foot
long mathematical formula that will blow my 30 year old high school
math away..
If this method is wanting, is there another way to create a
the desired DATA DIODE?
Thanks,
Green in New Hampshire
[EMAIL PROTECTED]
------------------------------
** 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
******************************
