Cryptography-Digest Digest #66, Volume #14 Tue, 3 Apr 01 08:13:00 EDT
Contents:
Re: Is this a solution to the PGP flaw (Lutz Donnerhacke)
Dynamic Substitution infringement? (Benjamin Goldberg)
Re: Data dependent arcfour via sbox feedback (Mok-Kong Shen)
Re: Idea - (LONG) (Mok-Kong Shen)
Re: Data dependent arcfour via sbox feedback (Mok-Kong Shen)
Re: Dynamic Substitution infringement? (Mok-Kong Shen)
Re: GCHQ turned me away...(we didn't think they understood) (Mok-Kong Shen)
Re: keys and random (Mark Wooding)
Re: efficient rabin signature? ("Bryan Olson")
Re: keys and random ("Henrick Hellström")
Re: AES VS. DES (Volker Hetzer)
Re: Public Domain MARS Implementation Source Code ("Brian Gladman")
RC4/ARC4 in hardware. ("Matt Hayes")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Lutz Donnerhacke)
Subject: Re: Is this a solution to the PGP flaw
Date: 3 Apr 2001 07:11:00 GMT
* lcs Mixmaster Remailer wrote:
>Even check after signing won't help, because if the attacker guessed
>right, the modified key is perfectly legitimate.
Right.
>So in effect we got a pseudo-signature with some extra bits in r and s.
>However I don't see how to exploit that. Maybe there'd be something
>you could do using a subgroup involving the factor j.
As typed yesterday: This is far behind my knowledge. Forwarded this thread
to a developer forum. Thanx.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Dynamic Substitution infringement?
Date: Tue, 03 Apr 2001 07:50:23 GMT
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?
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Data dependent arcfour via sbox feedback
Date: Tue, 03 Apr 2001 10:05:32 +0200
Terry Ritter wrote:
>
> I can't make anyone understand anything they don't want to. There is
> a substantial body of expertise needed to deeply understand patent
> claims, but many books and articles do discuss it, so you don't have
> to depend upon me. Patents are not necessarily logical, except in the
> details of patent law which you obviously do not understand. But,
> with study, an ordinary person can begin to understand the legal
> issues involved, although that means doing more than just arguing for
> the way you think things ought to be.
>
> As the sole inventor of several fundamental cryptographic
> technologies, I have had considerable experience with patents, but
> that still does not make me in any way an expert in patent law.
> Nevertheless, if you want to learn from the inventor himiself, you
> will have to accept what I say, and work at understanding that, or
> look into actual patent literature to correct errors I may have made.
> I have not been keeping up with changes, so some things may be
> different than they were.
>
> But, if -- as I suspect -- you just want to dispute, and complain
> about the unfairness of it all, either go away uninformed, or else
> find somebody who has time to waste.
>
> The concept of "substitution" is discussed throughout the patent, for
> example:
>
> * "A substitution or inverse substitution would typically
> be implemented as >>>addressable storage<<<, and realized with an
> electronic memory device, or an addressable area of memory hardware in
> an electronic digital computer or microprocessor."
>
> * "Substitution 12 can then be shuffled or randomized in any number of
> ways; as long as the values in the >>>table<<< are simply re-arranged
> or permuted, substitution 12 will remain invertible."
>
> * "Each plaintext character value selects an element in a
> substitution >>>table<<< . . . ."
>
> A table is a form of computation, but hardly an ambiguous concept.
Your statement that patents are not necessarily logical
simply shows the fact that the patent office employees
don't do their jobs properly. That a patent holder can't
clearly explain why his patent doesn't conflict with prior
art, while the very generally formulated claims of his
patent (unfortunately let through apparently without
thought by the patent office employees) clearly shows it
is, is extremely remarkable. Simply refering me to books
and others is in my view an indication that you yourself
don't fully know what your patent actually IS. Like
Hitachi's rotation patent, such stuffs are in my humble
view against what the patent laws are principally intended
for.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Idea - (LONG)
Date: Tue, 03 Apr 2001 10:18:25 +0200
Nicol So wrote:
>
> Mok-Kong Shen wrote:
> >
> > Nicol So wrote:
> >
> > > It's actually quite simple. Consider a source that outputs a sequence of
> > > 8-bit characters of even parity. Now a message of N characters consists
> > > of N*8 bits, but the amount of entropy needed to transmit the message
> > > with perfect secrecy is only N*7 bits. You don't need to expend 8 bits
> > > of shared randomness to perfectly mask a plaintext symbol--you can use
> > > an random even-parity character with only 7 bits of randomness.
> > >
> > > The point is: source characteristics affect the amount of key entropy
> > > required for perfect secrecy.
> >
> > ... But how about the case where he
> > doesn't have that knowledge? Does it help anything in
> > security? Thanks.
>
> If you don't know the exact amount of entropy in the plaintext, and
> still want to have perfect secrecy, you may be able to use a safe
> overestimate, depending on how much partial knowledge you have. In some
> cases, that may mean assuming the source to be potentially of maximum
> entropy, as a practical necessity. However, practical necessity is not
> what this (sub)thread is about.
To the sender, the plaintext is known and there is no
'entropy' for him. The entropy is context dependent, as
Douglas Gwyn pointed out in a thread some time back.
>
> In a previous message, you wrote:
>
> > If one has r bits of truly random bits (never mind how to
> > get this), one can *only* encrypt r bits with perfect
> > security in the sense of Shannon.
> [emphasis added]
>
> And Douglas Gwyn, apparently sensing a misappreciation of Shannon's
> result, responded and wrote:
>
> > Well, no, it depends on the source characteristics.
>
> Judging from your follow-ups, you didn't seem to get the point of the
> comment.
I pointed out that Gwyn was 'arguing about words'. Actually
I could counter about wordings. With respect to your example,
since the leading bit of a byte is 0 and is assumed to be
known to the opponent, it can be said that this bit does
not belong to the plaintext and so excluded from my 'r bits'.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Data dependent arcfour via sbox feedback
Date: Tue, 03 Apr 2001 10:27:21 +0200
Terry Ritter wrote:
>
>
> Any sequence of data values is "a source." We can see this throughout
> the patent, including: "A first data source and a second data source
> are combined into a complex intermediate form or result. . . ." Note
> the lack of description about the "ultimate" origin of any data
> sequence treated as a "source."
>
> Also note that the body description and diagrams represent one example
> of implementation, and do not limit the claims. This is patent law,
> but to make it clearer, it is explicitly stated at the end of the body
> text: "While my above descriptions contain many specificities, these
> should not be construed as limitations to the scope of the invention,
> but rather as an exemplification of a preferred embodiment thereof.
> Many other variations are possible. Accordingly, the scope of the
> invention should be determined not by the embodiments illustrated, but
> by the appended claims and their legal equivalents."
>
> And then we have the testimony from the claim itself:
>
> "
> 1(b) change means, at least responsive to some aspect of said second
> data source . . .
> "
>
> Note the phrase "some aspect of," clearly indicating that the second
> data source may be modified before being used in the "change means."
>
> But, if you don't like the word "source," perhaps you would prefer the
> word "value":
>
> "
> 15. A two-input one-output logic mechanism or design, which combines a
> first input value with a second input value, including:
>
> (a) substitution means, potentially including a plurality of
> storage means, for saving substitute values and translating said first
> input value into an output value, and
>
> (b) change means, at least responsive to some aspect of said
> second input value, for re-defining a proper subset of the substitute
> values within said storage means, potentially after every substitution
> operation.
> "
[snip]
> I'm not happy with any mechanism claimed to be Dynamic Substitution
> being inherently limited to a sequence of a particular length. It is
> implied throughout the patent body that there is no such limitation.
> Thus, I expect that the Dynamic Substitution patent distinguishes from
> the described mechanism. I think you can probably use it without
> patent implications.
All this clearly shows that even a classical polyalphabetical
substitution, combining a key stream with the plaintext
stream to produce a ciphertext stream, would also be
in conflict with the patent.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution infringement?
Date: Tue, 03 Apr 2001 10:31:31 +0200
Benjamin Goldberg wrote:
>
[snip]
> Does this infringe on the Dyn Sub patent?
Probably you would get an answer the same as what Terry
Ritter gave me, referring you to others and books and
asking you to do your studies (since you evidently don't
understand.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: GCHQ turned me away...(we didn't think they understood)
Date: Tue, 03 Apr 2001 10:38:52 +0200
Frank Gerlach wrote:
>
> I guess they just did what they do three times a week :-)
It is not clear what the OP meant by their turning him
away.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: keys and random
Date: 3 Apr 2001 09:02:16 GMT
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.
> Is the 2 hardcoded a problem ?
It makes finding appropriate Sophie-Germain primes even harder.
-- [mdw]
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Subject: Re: efficient rabin signature?
Date: Tue, 03 Apr 2001 09:38:43 GMT
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?
>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.
> 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.
>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.)
>[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.
>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.
--Bryan
------------------------------
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: keys and random
Date: Tue, 3 Apr 2001 12:21:39 +0200
"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.
And what is meant by a "random" prime? A new prime for each session, or a
unique long-term prime for each server? 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.
> 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.
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. For example, if you use a 1024 bit prime p = 2*q+1 and 256-bit
exponents, then K = 2**(xy) mod p will unequivocally determine x and y, but
this shouldn't be a problem because K is first hashed and then used to
initialize a secure cipher, so normally it would be as impossible for the
attacker to find K (and then xy), as to calculate the discrete logarithms of
a = 2**x mod p and b = 2**y mod p. For short, you don't have to increase the
size of the exponents until you begin to fear that your system is insecure,
and by then performance is probably not your major concern.
> > 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.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: AES VS. DES
Date: Tue, 03 Apr 2001 12:51:21 +0200
"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?
Greetings!
Volker
--
They laughed at Galileo. They laughed at Copernicus. They laughed at
Columbus. But remember, they also laughed at Bozo the Clown.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Public Domain MARS Implementation Source Code
Date: Tue, 3 Apr 2001 12:55:05 +0100
"Nathan J. Yoder" <[EMAIL PROTECTED]> wrote in message
news:jP6y6.1128$[EMAIL PROTECTED]...
> This may sound like a trivial/stupid question, but I am looking for an
> implementation of MARS that has been released in the public domain. I
have
> spent a long time search the web, mailing lists, and newsgroups and have
> found only one *open source* implementation that is *almost*, but not
quite
> public domain (the same for all websites/crypto archives etc..). This is
> the Brian Gladman implementation, the person who implemented several AES
> candidates for testing. IANAL, but if you read the license below, you'll
> see that you are required to give credit to the author (Dr. Brian
> Gladman) -- "acknowledgement of its origin" (similar to the MD5 reference
> implementation license). I admit that is a very small constraint, but I
am
> accumulating a personal source code repository (some of which will be used
> on some of my projects--one of which is a pure public domain crypto&ssl
lib
> *neat*) of strictly public domain (no constraints) source. I could
> implement it myself, but prefer to save time if possible.
>
> Also, I am slightly evil for not wanting that simple constraint (not
> acknowledging the author), but I'd rather not put an annoying notice in my
> software (though I'd still give credit for my open source versions of
> software that used it, just not the
>
I-want-to-make-money-by-selling-to-ignorant-windows-users-and-make-my-softwa
> re-look-special version). So I do have reasoning, and even the BSD people
> did the same thing when they took out the annoying advertising clause out
of
> the BSD license. You can see the license below of the software.
My MARS code was developed at a time when IBM placed constraints on the use
of the algorithm, which, no longer apply (as others have said). In
consequence some aspects of the header that I used at the time could now be
relaxed.
I have literally hundreds of emails from people asking if they can use my
code in their applications. I have not yet ever had to refuse such a request
and not one has yet asked if I would drop my requirement for a credit for
the work.
Most people seem to accept that this is a common courtesy that they would
willingly give irrespective of my request for it. Apart from anything else
it helps anyone who wants to rely on the code to be able to communicate with
the author in order to sort out issues when, for example, it is being ported
onto new processors. So it has practical value as well.
Brian Gladman
------------------------------
From: "Matt Hayes" <[EMAIL PROTECTED]>
Subject: RC4/ARC4 in hardware.
Date: Tue, 3 Apr 2001 12:55:43 +0100
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.
------------------------------
** 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
******************************
