Cryptography-Digest Digest #81, Volume #14 Thu, 5 Apr 01 07:13:00 EDT
Contents:
Re: rc4 without sbox swapping/updating (Terry Ritter)
Re: rc4 without sbox swapping/updating (Terry Ritter)
Re: TEA (Samuel Paik)
Re: patent this and patent that ("John A. Malley")
Re: Is this a solution to the PGP flaw ("Vlastimil Klima")
Re: PGP Private key cracking service ("r.e.s.")
Re: Data dependent arcfour via sbox feedback (Benjamin Goldberg)
Re: Newbie looking for texts about DES and Blowfish (Frank Gerlach)
Re: A gift for cryptanalysts (Mark Wooding)
Re: keys and random (Mark Wooding)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: rc4 without sbox swapping/updating
Date: Thu, 05 Apr 2001 05:22:07 GMT
On Wed, 04 Apr 2001 23:45:27 GMT, in <[EMAIL PROTECTED]>, in
sci.crypt Ken Savage <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>
>> >is dynamically adjusted, but the DynSub patent does not apply to this
>> >type of update (as far as I can tell.)
>>
>> "As far as you can tell?"
>>
>> Well, as far as *I* can tell, you have trouble reading. [...]
>
>
>> >Any comments greatly appreciated.
>>
>> I bet.
>
>
>As far as I can tell, I'm well able to read. While we may have
>different interpretations of what we're reading, it distracts from
>the DISCUSSION when snide comments find their way into replies.
I'll tell you what distracts from the DISCUSSION, and that is your
delusion that you have the expertise to make pronouncements and
conclusions in patent law. They are often wrong and misleading and
may do damage to the reputation of an issued patent. This is not a
toy patent just because you find it discussed on sci.crypt; you need
to be a great deal more careful.
>As my previous message indicates, there is an alternate way to
>interpret the claims in the patent. English, unfortunately, is
>not mathematics, which is the very reason these alternatives
>exist.
Patent claims must be interpreted within the context of the patent.
You don't get to supply just any meaning you want.
>I will admit that we both have different goals here; I am actively
>seeking a way to produce an rc4-compatible output stream without
>seemingly violating the Dynamic Substitution patent. Hopefully, the
>same techniques used in this endeavour can be used in other ciphers
>or realms. You, knowing that rc4 involves sbox updates, and being the
>holder of the DynSub patent, probably aren't too happy about these
>attempts :) I wouldn't blame you.
The issue is not one of goals, but fact.
The patent clearly does cover tables which are non-invertible:
"The combiner can also be used to combine two pseudo-random confusion
streams into a more-complex confusion stream. In this case, extraction
may be unnecessary and so the combiner substitution tables need not be
invertible."
The desirability of having non-invertible substitution tables is thus
part of the patent text. Absent a specific restriction otherwise in
the claim, that is what it may be. Any interpretation otherwise is
just silly.
>For me, it's not personal; I'm just doing my job (quite literally).
>I hope in the future this sentiment is reciprocated.
For me it is *both* personal *and* business. I find myself
simultaneously defending the cast-in-stone words in a patent which I
constructed a full decade ago, and also educating arrogant
pseudo-experts in the reality of patents and patent claims.
It is not your option to pick whatever definition you want for the
words in the claims. The words in the claims must be interpreted in
the context of the patent body.
In this case, the patent body clearly, specifically and unambiguously
describes using the patented mechanism with non-invertible tables to
mix two confusion sequences:
"The combiner can also be used to combine two pseudo-random confusion
streams into a more-complex confusion stream. In this case,
extraction may be unnecessary and so the combiner substitution tables
need not be invertible."
There simply can be no question about whether non-permutations were
considered acceptable in tables as part of the patent.
Since table contents are specifically allowed to be non-permutations,
you would have to find a limitation in the claim which said the table
needed to be a permutation. Independent claim 1 does not have that
limitation, and so does not require that aspect to be present in any
design matched to it. Something which is not specified is allowed to
be any way at all.
Surely you understand that it is only necessary to read on one claim
to have an example of the protected invention. Surely you understand
that anything beyond the limitations specified in the claims is not
relevant to the comparison.
Your views are simply not supported by the patent.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: rc4 without sbox swapping/updating
Date: Thu, 05 Apr 2001 05:22:57 GMT
On Wed, 04 Apr 2001 23:23:26 GMT, in <[EMAIL PROTECTED]>, in
sci.crypt Ken Savage <[EMAIL PROTECTED]> wrote:
>Terry Ritter wrote:
>
>> "The combiner can also be used to combine two pseudo-random confusion
>> streams into a more-complex confusion stream. In this case,
>> extraction may be unnecessary and so the combiner substitution tables
>> need not be invertible. Thus, the translation changes need not be
>> limited to permutations."
>
>In the case of rc4, extraction *IS* necessary. The above paragraph
>misses the case where extraction is required, yet the tables are not
>invertible.
No, the quote actually says (as anyone can easily see, above):
"extraction *MAY* be unnecessary." So even if extraction *is*
necessary, the quote still directly applies.
However, "extraction" has a very special sense in the context of a
patent which defines "combiner" and "extractor" mechanisms. If the
design does match the extractor claim, then of course the design reads
on the patent. If it does not, it is probably not an "extractor" in
the sense of the patent. So it is hard to know what you really mean.
>I'm finding that the PRECISE definitions of what is meant by "first
>data source", "second data source", "extraction", "invertible", etc
>are not clear.
>
>For instance, consider the sequence:
>
>0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, ...
>
>From an information-theoretic sense, this sequence is completely
>predictable, thus it has zero entropy, zero information and thus
>is not a data source. It's a "modulo-4 counter initialized to zero".
>
>Yet I suspect that any patent holder would gladly consider it a
>"data source" if it were profitable/advantageous for them to do so.
Yes, the patent holder generally has that option.
When a claim does not specify something, then, in general, every
option is permitted, and any option will still read on the claim.
>> Claim 1 has been presented verbatim many times. That claim does not
>> include a requirement that the "substitution means" must be
>> invertible. Instead, that comes in Claim 2:
>
>Definitions (from Webster's 9th new collegiate)
>
>Permutation: an ordered arrangement of a set of objects
>Permute: to change the order or arrangement of
>arrange: to put into a proper order or suitable sequence (note:
>SUITABLE)
>re-arrange: to arrange anew
>
>Claim 1b: "... for permuting or re-arranging ... within said
>substitution means"
>
>To be noted:
>
>1) The code presented does not permute any values
>2) No ordering is done on add[], nor is any suitability determined.
>3) Since no permutation is done, nor any suitability determined,
>it is not a re-arrangement.
>
>In more layman's terms, to "rearrange your furniture" means to take
>your furniture, and reposition them about your house. You still have
>the same furniture. If I was asked to "rearrange the elements in
>this array", I would shuffle the array ---- KEEPING THE SAME VALUES
>AS WAS IN THE ARRAY, instead ** PERMUTING ** them. Synonym.
>
>
>As such, I don't see my code passing (1b).
>
>> 2. The combining mechanism of claim 1 wherein said substitution means
>> is initialized to contain at most one occurrence of any particular
>> translation.
>
>My code doesn't pass (2).
>
>> Claim 1 does read on tables which are non-invertible.
>
>Provided they are permuted.
"
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.
"
Notice the term "re-defining" instead of "permuting."
You do understand that a design will read on a patent if *any* claim
in it is satisfied, right?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Samuel Paik <[EMAIL PROTECTED]>
Subject: Re: TEA
Date: Thu, 05 Apr 2001 05:44:31 GMT
Dave Mennenoh wrote:
> Anyway, I got hold of the TEA algorithm and ported it to Lingo - Director's
> scripting language.
>
> I could not do the port exactly as the algorithm does as Lingo doesn't
> handle large integers.
You don't need to handle large integers for TEA. If your language
doesn't support 32-bit addition, You can implement multi-precision
addition in whatever width addition your langauge actually handles.
[I've written TEA in assembly for an 8-bit processor]
Sam Paik
--
Samuel S. Paik | [EMAIL PROTECTED]
3D and digital media, architecture and implementation
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: patent this and patent that
Date: Wed, 04 Apr 2001 22:47:59 -0700
Terry Ritter wrote:
>
[snip]
>
> My point here is that I would think Company A is more in the driver's
> seat than you indicate. If A has been "blocked," surely that is a
> natural result of not building on their original lead in technology.
> When companies get old, they get sold, and life goes on.
>
Company A is at a disadvantage when it's a start-up or a fledgling/young
business and Company B is an established company in the same
marketplace. Company B innovates but transitions "bleeding-edge"
discoveries to market at a slower, more measured and cautious rate than
a no-holds-barred startup ever would.
Scenarios like this (I've been told) play out in the semiconductor/chip
world. Upstarts take on daring and media-darling "great-leaps-forward";
the established giants let the start-up sort the technology out and get
a few key patents. Then the giant patents about the start-up's patents.
A start-up cannot take the financial pressure of blocking patents when
its product line is so new, non-diversified and economically fragile.
Eventually an interested giant gets access to the technology either
through generous licensing deals or outright purchase of the weakened
start-up.
And "60 Minutes" on CBS in the States (years ago) ran a story on a small
high-tech American business that tried to establish its product in
Japan. It filed Japanese patents covering its invention. A Japanese
company "patented about their patents" and blocked the growth of the US
company's market presence in Japan. The Japanese company offered to
license their improvements to the American company's invention in return
for extremely generous licensing terms on the American's Japanese patent
and (if memory serves) on their US patent as well, so the Japanese
company could sell its product in the US and compete more effectively
against the US company.
The US company eventually lobbied its local Congressman to bring
political pressure on the Japanese government. I seem to recall the US
company ended up leaving the Japanese market.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Vlastimil Klima" <[EMAIL PROTECTED]>
Subject: Re: Is this a solution to the PGP flaw
Date: Tue, 3 Apr 2001 12:00:10 +0200
Great observation!
In the article "Breaking Public Key Cryptosystems on Tamper Resistance
Devices in the Presence of Transient Faults" by Bao, Deng, Han,
Jeng,Narasimhalu and Ngair (Security Protocols, 1997, Springer-Verlag, LNCS
vol. 1361, pp.115-124) is a very similar idea.
Your attack needs more iterations, but it is very interesting.
In our paper ( http://www.i.cz/en/pdf/openPGP_attack_ENGvktr.pdf), section
7, we proposed "temporary tests (say for a patch) " and "future
countermeasures". On the temporary tests we said
"....We stress out that the aforesaid test is not to be a substitute for the
missing check of integrity of the file with the private key but it is to
serve as a temporary measure which prevents the herein specified attack..."
and at section 7.2 we said:
"...Let us also note that whereas such type of tests as we already mentioned
is trusted a lot, for instance in RSA, in case of DSA we have to be careful.
Unlike RSA there is only one value here (private key x), unknown by the
attacker. Other parameters are known by the attacker and it may change them
at its own discretion. This is a reason, why this test is considered only a
temporary solution, which must be replaced as soon as possible with another
type of check of integrity of the discussed records, as hereafter specified.
"
Our recommendations are expressed in section 7.4 of the paper.
Vlastimil Klima and Tomas Rosa
"lcs Mixmaster Remailer" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Here is another variant on the attack which will still work even if
> the recommended mathematical checks are done. However it leaks only a
> small amount of information about the secret key.
>
> We have g^q = 1 mod p; g^x = y mod p; q | (p-1), etc. Now suppose an
> attacker wants to learn if x is even or odd.
>
> He can toggle the low order bit of x by xoring into the ciphertext.
> As is well known, in CFB mode, such an xor goes through to the
> plaintext at the cost of disturbing the following block of plaintext.
> (CBC has similar properties, but with the roles of the two plaintext
> blocks reversed.)
>
> Toggling the low order bit of x will either increment it or decrement
> it, depending on whether x is even or odd. This will cause y to be
> either multiplied by g, or divided by g.
>
> The attacker makes a guess about x being even or odd, toggles the bit
> and adjusts y accordingly. (He also has to adjust the checksum, which
> he can do with 50% success.) The resulting key is perfectly
> consistent mathematically, if his guess was correct.
>
> Then he sees if the user is able to use the key, or if he gets an
> error. If there is no error, the attacker knows he guessed right
> about the low bit of x.
>
> In some circumstances it may be possible for the attack to be mounted
> repeatedly and gradually learn more bits. For example, if the attack
> is possible because the key is stored on a network file system, as Dr.
> Klima proposes, the user may re-run PGP repeatedly when he gets an
> error, thinking he is typing his passphrase wrong. In some
> configurations this will re-fetch the secret key ring each time, and
> the attacker can modify a different bit of x each time. He can learn
> almost 128 bits of x in the best case. With this advantage, brute
> forcing the remaining bits of x may be possible.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: PGP Private key cracking service
Date: Wed, 4 Apr 2001 23:34:59 -0700
"Jim Gillogly" <[EMAIL PROTECTED]> wrote ...
| Peter wrote:
| >
| > I forgot my passphrase...
| > Are there any tools I could use to try to crack my private key
passphrase?
| > Is there a (commercial) service that does this for me?
|
| Tools have been written to do this -- you might try a web search.
| If you were at all sensible with your passphrase selection you're
| totally out of luck, and you'll need to create a new key and write
| off any encrypted data you left lying around. On the other hand,
| if you're the type that picks a dictionary word or a date, you have
| a good chance of recovering it.
Still, even if an "excellent" passphrase had been used,
surely the difficulty of recovering it is a function of
how much about it might be remembered. Maybe the OP can
recall sufficient clues about the password, that a
feasible search by some commercial service is not out
of the question?
--r.e.s.
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Data dependent arcfour via sbox feedback
Date: Thu, 05 Apr 2001 07:23:55 GMT
Terry Ritter wrote:
>
> On Wed, 04 Apr 2001 19:53:09 -0700, in
> <[EMAIL PROTECTED]>, in sci.crypt Bryan Olson wrote:
[snip]
> >You also went through the claim and showed DES obviously
> >does't match. Shouldn't this algorithm be handled the same
> >way?
>
> Yes, it should and was. DES is not a substitution table.
What are smoking, and can I have some? DES is most certainly a
substitution, though not a simple table. However, it *can* be modeled
as a [64x64 bit] table. Any change in the DES key permutes the table
which the DES algorithm models. Thus, key feedback mode can be
considered prior art to Dynamic Substitution.
--
Sometimes the journey *is* its own reward--but not when you're trying to
get to the bathroom in time.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Newbie looking for texts about DES and Blowfish
Date: Thu, 05 Apr 2001 10:00:00 +0200
get "Applied Cryptography" by Bruce Schneier. Definitely worth what it
costs.
John Stanford wrote:
> I'm new to cryptography. Can anyone tell me where I can find texts
> about how Blowfish and DES work? Thanks
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: A gift for cryptanalysts
Date: 5 Apr 2001 10:18:03 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> However, by adapting the general idea, I believe I have found a differential
> over 15 rounds that exists with probability circa 2**-60.
Good work. Thanks for saving me from astonishment. ;-)
Hmm. I *should* now give up and go back to my day job. But rather than
throw in the towel, I'll try to rescue my bad idea...
> Input delta 0x80000000 => Output delta 0x00008000 (probability 1)
> Input delta 0x00008000 => Output delta 0x80000000 (probability 2**-15)
D'oh! I'd sort of noticed that, but decided that the probability was too
low. My fault for not actually doing the arithmetic!
I first note that widening the block makes the differentials
correspondingly improbable. For example, a 128-bit wide Gift has a
similarly-structured differential with probability 2^{-120}. So I'll
think about a generalized Gift with b-bit blocks.
Secondly, Gift is holding up much better than I expected!
Anyway, on to the tweaking...
Adding C rather than XORing would fix this good and proper. The carries
in the addition will square the differential probabilities. This is a
somewhat ugly patch, though. (I didn't want to use addition here,
because it makes the cipher too +/*-linear. I still don't.)
The problem seems to be an unwanted symmetry caused by the rotation
constant. What does changing it from b/4 (b being the block width in
bits) to some arbitrary r do to the differentials?
Following Knudsen, I'll define t_i = 2^{b - 1 - i} (subscripts in this
notation being implicitly reduced mod b); then we have
t_i -> t_{i+r}
with probability 2^{-i} through F. Now all we need to do is follow it
through the Feistel structure. ;-)
Unfortunately, life gets difficult when we try to push these through the
Feistel structure. We have the obvious differentials
(0, x) -> (x, 0) [0]
(t_i, 0) -> (t_{i-r}, t_i) [i]
(t_i, t_{i-r}) -> (0, t_i) [i]
(Numbers in [...] are -log_2 of probability.)
Starting with the last differential...
(t_i, t_{i-r}) -> (0, t_i) [i]
(0, t_i) -> (t_i, 0) [0]
(t_i, 0) -> (t_{i-r}, t_i) [i]
and then we're stuck unless i - 2r = i (mod b), because the notation
doesn't do more than one bit...
Let's extend the t-notation. Let t_{a_0,a_1,...,a_n}, for distinct a_i,
be \sum_{0<=i<n} t_{a_i}.
Now
(t_{i-r}, t_i) -> (t_{i,i-2r}, t_{i-r}) [i - r]
But what will multiple bits do? It gets a bit complicated, but there
are some things we can do to make life easier on ourselves.
We'll take a break to examine the behaviour of t_{i,j} through F
(assuming, WLOG, i < j). If i - (b - 1 - j) >= 0 then we'll get
something like
t_{i,j} -> t_{i-r,j-r,i-r-(b-1-j)} [j]
Since the probability of the differential is related to the
least-significant bit in the input, having more bits build up is a
pain. But! if i - (b - 1 - j) < 0, we have
t_{i,j} -> t_{i-r,j-r} [j]
because the other bit fell off the end.
Continuing this analysis looks painful. These bits aren't going to be
cancelling each other out any time soon, and we'll end up with n - 3
rounds (assuming we set i = 0) of 2^{-b/4} probability differentials at
best. I think that's secure against this attack after 7 rounds, and I
have 16.
Any more for any more?
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: keys and random
Date: 5 Apr 2001 10:51:16 GMT
David Wagner <[EMAIL PROTECTED]> wrote:
> Mark Wooding wrote:
> >There are some sly active attacks against Diffie-Hellman exchanges and
> >similar which force values into different subgroups. You resist these
> >attacks by (a) noticing when something is in the trivial subgroup (1,
> >-1) and (b) making sure that it doesn't matter when this happens because
> >all the other subgroups are at least as difficult as your main one
> >anyway.
>
> I agree with your first statement, but I'd like to see some
> further evidence for the second one. What if I replace g^x
> (in the subgroup) by - g^x? This won't be detected by your
> measures, but I can easily imagine using it to attack a protocol.
> (For instance, suppose the receiver computes (g^x)^y, where y
> is a long-term secret. Then the resulting key exchange will
> succeed iff y is even, potentially revealing one bit of
> information on y per key exchange.)
Errr... surely only one bit of y ever. y doesn't change its evenness
between protocol exchanges. (I can see how to find s if y = 2^s t and t
is odd by repeated games of this nature, not beyond.)
That wasn't actually the sort of thing I was thinking about, though: I
was concerned about sending out public values in smooth subgroups, which
would reveal potentially the entire secret. So you raise a valuable
point.
Finally, this attack doesn't reveal a security difference between
Lim-Lee and Sophie-Germain primes, which was the main point of my
article.
[It's at this point I breathe a slight sigh of relief. My own protocols
tend to use ephemeral Diffie-Hellman for key exchange, and in the
authentication step the verifier provides a hash of the expected answer,
proving that it's not a trick question or been fiddled with.]
> It seems to me that it would be prudent to check that all
> received values that are supposed to be in the subgroup are
> indeed in the subgroup. This can be done by checking that
> X = g^x is not 1, and that X^q = 1 mod p, if q is prime.
This is good advice.
-- [mdw]
------------------------------
** 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
******************************
