Cryptography-Digest Digest #67, Volume #14 Tue, 3 Apr 01 11:13:01 EDT
Contents:
Re: efficient rabin signature? ("Tom St Denis")
Re: AES VS. DES ("Tom St Denis")
Re: RC4/ARC4 in hardware. ("Tom St Denis")
Re: keys and random ("Tom St Denis")
Re: Dynamic Substitution infringement? ("Tom St Denis")
Re: RC4/ARC4 in hardware. (Frank Gerlach)
Re: RC4/ARC4 in hardware. (Frank Gerlach)
Re: GCHQ turned me away...(we didn't think they understood) (John Savard)
Re: AES VS. DES (John Savard)
Re: Data dependent arcfour via sbox feedback (John Savard)
A gift for cryptanalysts (Mark Wooding)
Re: keys and random (Mark Wooding)
Re: GCHQ turned me away...(we didn't think they understood) - Off Topic ("John A.
Malley")
Re: keys and random (Mark Wooding)
Blowfish in Fortran? (Stephan Petersen)
Re: AES VS. DES (William Hugh Murray)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: efficient rabin signature?
Date: Tue, 03 Apr 2001 12:11:06 GMT
""Bryan Olson"" <"nospam"@"nonsuch.org"> wrote in message
news:DSgy6.1$eq5.91@interramp...
> Tom St Denis wrote:
> >This has most likely been proposed before... but here is an idea I was
just
> >thinking of..
>
> I think a standard for verify-efficient Rabin signatures
> (with appendix) is a good idea. There are some tricky
> points.
>
> >The secret key is <p,q> which are two large primes (congruent to 3 mod 4)
> >such that N=pq is a blum integer. To sign a message you perform the
> >following.
> >
> >1. K = (hash of message) * 65536
>
> How did you choose 2^16?
Well any size. The idea is that you increment the lsbs until you hit a good
one.
> >2. if J(N, K) = 1 then solve for the principal square root of K
>
> Half the values k such that J(N, k) = 1 do not have a square
> root mod N (where N is a Blum integer). Fortunately, since
> the signer knows p and q, he can check both Legendre symbols
> to determine whether it's a quadratic residue.
I thougth the Jacobi and Legendre symbol were equivelant for odd N? Isn't
the jacobi used in the QS factoring to find good factor base primes? i.e
J(N, Pi) != -1?
> > and store it in M and goto step 4
>
> A conventional hash digest is too small. You must use a
> full-domain hash or pad K. Padding for Rabin signatures
> is tricky.
Ah...well you could pre-append 1 bits so you get 111111111...etc || hash ||
binary_counter. That way it won't have answers in Z ever.
> >3. If J(N, K) = -1 then increment the lower 16 bits of K and goto 2
>
> As noted above, you need to skip all the non-QR's.
>
> I don't think giving away the non-QR status of the rejected
> K values where J(N, K) = 1 hurts, but can you prove it's
> safe? If not, I suggest generating the candidates in a
> key-dependant order, so the verifier couldn't tell what
> numbers were rejected. (I wouldn't use a random order,
> since that would produce multiple signatures for the same
> message.)
Well the bottom L bits could be made by BBS? I.e use the message hash as a
seeking point into the BBS output then just output L bit words until the
entire word is a QR?
>
> >[4]. Output M
> >
> >To verify you simply do
> >1. K = M^2 mod N
> >2. Divide K by 65536
> >3. Compare K against the hash of the message.
>
> So for a typical message, there are about 16000 other
> signatures that will verify.
Why?
>
> >Obviously some modifications can be made for example storing the lower 16
> >bits along with M such that they can be compared.
>
> What good is that? They're outside the signature so I don't
> see the point.
>
> > Also modifying the upper bits of K as (if) required.
>
> Padding, or a full-domain hash, is definitely required.
> Simple fixed padding makes for a more efficient verifier,
> but full-domain hashing is considered safer.
>
> I'd add a couple requirements: For security, N must be at
> least 1024 bits. To make the verifier as simple and
> efficient as possible, N must be a multiple of 256-bits in
> length, and the most significant 65 bits of N must all be 1.
All good, Thanks for the reply.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: AES VS. DES
Date: Tue, 03 Apr 2001 12:11:42 GMT
"Volker Hetzer" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Douglas A. Gwyn" wrote:
> >
> > Volker Hetzer wrote:
> > > There are methods better than exhaustive key search.
> >
> > Actually, no, not under normal circumstances.
> So, what do you consider "normal" circumstances?
A "random" 256-bit key, using the cipher in CTR mode?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RC4/ARC4 in hardware.
Date: Tue, 03 Apr 2001 12:18:48 GMT
"Matt Hayes" <[EMAIL PROTECTED]> wrote in message
news:3ac9b9a6$[EMAIL PROTECTED]...
> I'm aware that quite a number of people believe that the RC4 algorithm
isn't
> particularly suited to hardware but the idea interests me nonetheless.
>
> I have performed a few websearches but can't really find the answers I am
> looking for.
>
> In particular, I would like to know:
> a) what rates of data throughput have been achieved by RC4 implementations
> in hardware? what is the fastest ever?
> b) if it is possible to purchase a fast RC4/ARC4 IP Core and what
throughput
> rates can be expected.
The problem with RC4 is that it not only requires the ram but it execution
is inherantly serial. Hardware would only be more efficient then a
processor (like the Athlon) in the sense that "redtape" would be removed.
It couldn't for example process two bytes at the same time.
Why not consult "opencores.org" about your query?
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: keys and random
Date: Tue, 03 Apr 2001 12:19:53 GMT
"Mark Wooding" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Brian D Jonas <[EMAIL PROTECTED]> wrote:
>
> > p is a sophie germain RANDOM prime, which is what is recommended
> > EVERYWHERE on the net for diffie hellman key exchanges.
>
> Is it? Oh, well. I recommend *against* Sophie-Germain primes. I think
> you'd be wasting your time if you tried generating these.
>
> Generating Lim-Lee primes is only a little harder than generating random
> primes, and the result is as good as a Sophie-Germain prime against any
> attack I know of. Performance in use is also better, since your
> exponents are shorter.
What are LL primes? AFAIK SG primes are the strongest against any index
calculus based method because of the large subgroup.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution infringement?
Date: Tue, 03 Apr 2001 12:21:08 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In a recent [still active] thread about an RC4 variant, there was some
> discussion about what kinds of things infringe on Terry Ritter's patent.
>
> I would like some comments on what people believe should be covered by
> the patent, and what shouldn't. Also, I would like to see some
> suggestions on what might be the simplest infringing cipher or cipher
> component.
>
> Here's one suggestion:
>
> byte mix2(byte x, byte y) {
> static bool state = 0;
> byte output;
> output = state ? (x+y) : (x^y);
> state ^= output & 1;
> return output;
> }
>
> Does this infringe on the Dyn Sub patent?
I dunno but you realize that your state boolean and your mixing in the lsb
are all xor-linear?
Tom
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: RC4/ARC4 in hardware.
Date: Tue, 03 Apr 2001 14:39:33 +0200
I guess an ASIC could implement it quite efficiently, but because of the large
state memory an FPGA doesn't seem to be a good idea.
Speeding up a single RC4 stream seems to be difficult, but who said there cannot
be multiple RC4 streams either from an ASIC or by using VLIW software
instructions.
Also, the Intel Random Number Generator could be a nice tool to produce
high-quality keymat for a One-Time-Pad at high speed. Just make sure nobody rigs
the Pentium masks :-)
Or they declare Pentiums a weapon....
Matt Hayes wrote:
> I'm aware that quite a number of people believe that the RC4 algorithm isn't
> particularly suited to hardware but the idea interests me nonetheless.
>
> I have performed a few websearches but can't really find the answers I am
> looking for.
>
> In particular, I would like to know:
> a) what rates of data throughput have been achieved by RC4 implementations
> in hardware? what is the fastest ever?
> b) if it is possible to purchase a fast RC4/ARC4 IP Core and what throughput
> rates can be expected.
>
> Thanks,
>
> Matt.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: RC4/ARC4 in hardware.
Date: Tue, 03 Apr 2001 14:41:30 +0200
With VLIW I refer to the 8bit multimedia instructions. Could actually be a nice tool
for codebreaking...
Frank Gerlach wrote:
> I guess an ASIC could implement it quite efficiently, but because of the large
> state memory an FPGA doesn't seem to be a good idea.
> Speeding up a single RC4 stream seems to be difficult, but who said there cannot
> be multiple RC4 streams either from an ASIC or by using VLIW software
> instructions.
>
> Also, the Intel Random Number Generator could be a nice tool to produce
> high-quality keymat for a One-Time-Pad at high speed. Just make sure nobody rigs
> the Pentium masks :-)
> Or they declare Pentiums a weapon....
>
> Matt Hayes wrote:
>
> > I'm aware that quite a number of people believe that the RC4 algorithm isn't
> > particularly suited to hardware but the idea interests me nonetheless.
> >
> > I have performed a few websearches but can't really find the answers I am
> > looking for.
> >
> > In particular, I would like to know:
> > a) what rates of data throughput have been achieved by RC4 implementations
> > in hardware? what is the fastest ever?
> > b) if it is possible to purchase a fast RC4/ARC4 IP Core and what throughput
> > rates can be expected.
> >
> > Thanks,
> >
> > Matt.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: GCHQ turned me away...(we didn't think they understood)
Date: Tue, 03 Apr 2001 13:08:50 GMT
On Tue, 03 Apr 2001 10:38:52 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>It is not clear what the OP meant by their turning him
>away.
To me, it was obvious. The GCHQ failed to express interest in some
sort of deal or agreement whereby the OP would keep his new
unbreakable cipher secret so that the GCHQ could continue reading
people's mail.
Sounds like the mentality of a lot of people who post to this group:
"I've just come up with the world's first totally unbreakable cipher
(not counting the OTP)" and so on. It is not surprising that the GCHQ
had a lack of interest, considering that nearly everybody else also
lacks interest in this sort of thing.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: AES VS. DES
Date: Tue, 03 Apr 2001 13:16:14 GMT
On Tue, 03 Apr 2001 12:51:21 +0200, Volker Hetzer
<[EMAIL PROTECTED]> wrote, in part:
>"Douglas A. Gwyn" wrote:
>> Volker Hetzer wrote:
>> > There are methods better than exhaustive key search.
>> Actually, no, not under normal circumstances.
>So, what do you consider "normal" circumstances?
I think he meant, specifically, for DES.
This is true; all methods for breaking single-DES with complexity less
than 2^56 require far larger amounts of known plaintext than is likely
to be obtained in practice for any one key.
Particularly, say, if one is intercepting the radio transmissions of a
foreign military. You would be surprised how hard it is to transmit,
say, 2^32 blocks of chosen plaintext on their radios without anyone
noticing and changing the key.
Of course, that doesn't change the fact that the existence of a
theoretical attack with less than 2^56 complexity indicates there is a
degree of weakness in the design of DES. However, a very small degree,
considering the nature of the attacks so far known. Since brute-force
search on a 56-bit key is now feasible, DES can be considered "broken"
even in the absence of such attacks.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Data dependent arcfour via sbox feedback
Date: Tue, 03 Apr 2001 13:18:48 GMT
On Tue, 03 Apr 2001 04:05:02 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
in part:
>Next, from the Dynamic Substitution patent, the 6th paragraph under
>the Objects and Advantages section:
>"Another object of this invention is to provide a mechanism or process
>by which two confusion sources can be combined to produce a
>more-complex confusion result which may be used by some other combiner
>mechanism."
In that case, RC4 does infringe the Dynamic Substitution patent,
unless this object was nowhere included in the claims.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: A gift for cryptanalysts
Date: 3 Apr 2001 13:51:38 GMT
The other day I was thinking about a block cipher I could implement
easily in my HP-48 calculator. I wanted to avoid tables and polynomial
arithmetic, because it's too painful, and I wanted to minimize memory
usage as much as possible. I didn't care about performance.
I constructed a 64-bit block cipher with a 128-bit key. I used 32-bit
integer multiplication, OR, XOR, and fixed rotations. There is a magic
constant, C = 0xb7e15163.
The cipher, Gift, is a 16-round Feistel network.
We define the function F_z(x) for two 32-bit words x and z, to be:
F_z(x) = ((x * (z OR 1)) XOR C) <<< 16
where * denotes multiplication mod 2^{32}, OR denotes bitwise
inclusive-OR, XOR denotes bitwise exclusive-OR and <<< denotes a
circular left shift.
The key schedule constructs 18 32-bit subkeys from the 4 32-bit key
(k_0, k_1, k_2, k_3):
z_i = F_{k_{i+3}}(k_{i+1})
k_{i+4} = k_i XOR z_i
for 0 <= i < 18. The z_i are the round subkeys.
To encrypt a block represented as a pair of 32-bit words (x_0, x_1):
Let x_2 = x_0 XOR z_0. Now define
x_{i+3} = x_{i+1} XOR F_{z_{i+1}}(x_{i+2})
for 0 <= i < 16. Then let x_19 = x_17 XOR z_17. The ciphertext is the
pair (x_19, x_18).
I wanted to save code by using the same F function in the key schedule
and cipher. The key schedule can be run backwards as well as forwards,
so for decryption you just need to remember (k_{18}, k_{19}, k_{20},
k_{21}) on a long-term basis. The keys are used in the order they're
generated. Apart from the key schedule, decryption is the same as
encryption.
The function F_z is bijective. (z OR 1) is coprime to 2^{32}, so the
multiplication is invertable. XOR with a constant, and fixed rotation
are obviously bijective. However, it's not possible, in general, to
determine z given x and F_z(x), since x might be even.
The multiplication is easy on the HP-48, and provides good upwards
diffusion. The only problem is that if x = 0, x * z = 0 too; hence the
XOR. The rotation provides downwards diffusion.
I think that we get total avalanche in the cipher within four rounds.
The key schedule avalanches well too. Note that at each stage the
output of the previous Feistel-like round is used as the key in the next
one in the forward direction; in the backwards direction, we get strong
avalanche because of the Feistel structure of the key schedule.
There's no particular reason not to allow other block sizes. The
rotation should be by a quarter of the block size. Similarly, different
sized keys can be accommodated by minor and obvious tweaks to the key
schedule.
The multiplication should sort out any problems with differential or
linear cryptanalysis extremely rapidly. I think I'm mainly worried
about techniques like mod-n analysis.
I'll be astonished if Gift is actually strong. It's just too simple.
And too fast. It's *very* fast. 50% faster than Blowfish (Catacomb
version, on a P3).
Gift is free to everyone, for any use.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: keys and random
Date: 3 Apr 2001 14:00:00 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
> > Generating Lim-Lee primes is only a little harder than generating random
> > primes, and the result is as good as a Sophie-Germain prime against any
> > attack I know of. Performance in use is also better, since your
> > exponents are shorter.
>
> What are LL primes? AFAIK SG primes are the strongest against any index
> calculus based method because of the large subgroup.
I didn't think that index-calculus methods cared much about the subgroup
structure of field.
A Lim-Lee prime p = 2 q_0 q_1 ... q_n + 1 where the q_i are all `large'
-- large enough to dissuade collision-finding attacks such as Pollard's
rho. Thus, except for the trivial subgroup, all subgroups are large
enough not to be a problem. And you don't have to worry about evil
people forcing you into smooth-ordered subgroups, because there aren't
any.
You generate Lim-Lee primes by making a collection of q_i candidates and
multiplying them together in various combinations until you get a prime
out the far end. GnuPG generates Lim-Lee primes for DSA and ElGamal, if
I remember correctly. Catacomb also generates Lim-Lee primes if you so
wish.
-- [mdw]
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: GCHQ turned me away...(we didn't think they understood) - Off Topic
Date: Tue, 03 Apr 2001 07:02:20 -0700
John Savard wrote:
>
[snip]
>
> Sounds like the mentality of a lot of people who post to this group:
> "I've just come up with the world's first totally unbreakable cipher
> (not counting the OTP)" and so on. It is not surprising that the GCHQ
> had a lack of interest, considering that nearly everybody else also
> lacks interest in this sort of thing.
>
The phenomenon is interesting with respect to the history of technology
and invention in western cultures.
The claims and the rhetoric about unbreakable ciphers fit a pattern
common to perpetual motion machines as described in "Perpetual Motion
Machines, The History of an Obsession" by Arthur W.J.G. Ord-Hume, ISBN
0-312-60131-X. I wonder if this role must appear in new guises as
technology evolves through the "Machine Age." I'm watching for the
first signs of its equivalent in the biotechnology arena ( potential
candidate: grandiose claims and rhetoric about cloning from a garage DNA
splicer.)
Intuitive or "folk" physics and mathematics (especially naive concepts
of probability) prior to education trip people up in simple hands-on
experiments. These experiments hint at basic cognitive processing we all
share. It's hypothesized these intuitive concepts of physics and
mathematics improved our survivability as a species, but, these
intuitions are not strictly mathematically or physically correct.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: keys and random
Date: 3 Apr 2001 14:10:33 GMT
Henrick Hellstr�m <[EMAIL PROTECTED]> wrote:
> "Mark Wooding" <[EMAIL PROTECTED]> skrev i meddelandet
> news:[EMAIL PROTECTED]...
> > Brian D Jonas <[EMAIL PROTECTED]> wrote:
> >
> > > p is a sophie germain RANDOM prime, which is what is recommended
> > > EVERYWHERE on the net for diffie hellman key exchanges.
> >
> > Is it? Oh, well. I recommend *against* Sophie-Germain primes. I think
> > you'd be wasting your time if you tried generating these.
>
> It is not a waste of time if they are to be hardcoded. I managed to
> generate a 2048 bit Sophie-Germain prime in less than one hour on a
> pIII computer simply by running parallel Miller-Rabin tests on p and
> q.
Well, in that there's no security advantage to generating an S-G prime
compared to an L-L prime, and L-L primes are *much* faster to find, I'd
say it's still a waste of time. I just asked for a 2048-bit L-L prime
with 256-bit factors; it took 44 seconds.
I claim, therefore, that you wasted almost an hour finding your Sophie-
Germain prime.
(By the way, I think you struck lucky when you found a 2048 S-G prime in
under an hour. I've waited longer than that for 1024-bit S-G primes.)
> And what is meant by a "random" prime? A new prime for each session, or a
> unique long-term prime for each server?
Just one that's chosen at random, rather than having any particular form.
> I don't think the former is doable given the average contemporary
> server computer with a modest work load, and the latter would not give
> you that much security benefit over a hardcoded prime.
I completely agree with both statements. I approve of hardcoded primes,
just not Sophie-Germain ones.
> > Performance in use is also better, since your exponents are shorter.
>
> I might have missed something, but I don't think this is an issue. You
> don't have to use exponents that are as wide as the order of the group
> you move in.
True, but you might as well have a smaller group here. The attacks are
still square-root in the maximum exponent.
> > > Is the 2 hardcoded a problem ?
> >
> > It makes finding appropriate Sophie-Germain primes even harder.
>
> Only by a factor of 2. If 2 isn't a generator of Z*(p), it is a generator of
> the large subgroup of order q.
Yes, indeed. But it *is* harder. ;-)
-- [mdw]
------------------------------
From: Stephan Petersen <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.fortran
Subject: Blowfish in Fortran?
Date: Tue, 03 Apr 2001 14:30:26 +0000
Does anybody know of a Blowfish implementation in Fortran (77) ?
Thanks in advance for any pointers,
Stephan
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: AES VS. DES
Date: Tue, 03 Apr 2001 14:37:07 GMT
John Savard wrote:
> On Tue, 03 Apr 2001 12:51:21 +0200, Volker Hetzer
> <[EMAIL PROTECTED]> wrote, in part:
> >"Douglas A. Gwyn" wrote:
> >> Volker Hetzer wrote:
>
> >> > There are methods better than exhaustive key search.
>
> >> Actually, no, not under normal circumstances.
>
> >So, what do you consider "normal" circumstances?
>
> I think he meant, specifically, for DES.
>
> This is true; all methods for breaking single-DES with complexity less
> than 2^56 require far larger amounts of known plaintext than is likely
> to be obtained in practice for any one key.
>
> Particularly, say, if one is intercepting the radio transmissions of a
> foreign military. You would be surprised how hard it is to transmit,
> say, 2^32 blocks of chosen plaintext on their radios without anyone
> noticing and changing the key.
>
> Of course, that doesn't change the fact that the existence of a
> theoretical attack with less than 2^56 complexity indicates there is a
> degree of weakness in the design of DES. However, a very small degree,
> considering the nature of the attacks so far known. Since brute-force
> search on a 56-bit key is now feasible, DES can be considered "broken"
> even in the absence of such attacks.
While still quite useable in applications where the value of the data
encrypted under a single key is dramatically lower than the cost of such
attacks and/or the life of the data shorter than the duration of such an
attack. That said, 3-DES is less than 4 times as expensive as DES and not
"broken."
>
>
> John Savard
> http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
