Cryptography-Digest Digest #58, Volume #12 Sun, 18 Jun 00 23:13:01 EDT
Contents:
Re: small subgroups in Blum Blum Shub (David A. Wagner)
Re: small subgroups in Blum Blum Shub (David A. Wagner)
Re: AWFUL PUN (was: Why the golden ratio?) (John Savard)
Re: AWFUL PUN (was: Why the golden ratio?) (John Savard)
Re: small subgroups in Blum Blum Shub (Mark Wooding)
Re: Weight of Digital Signatures ("Lyalc")
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: small subgroups in Blum Blum Shub (Terry Ritter)
Re: Q: Equally like bit-flips in a Gray code? (Tim Tyler)
Re: Equally like bit-flips in a Gray code? ("Scott Fluhrer")
Re: Equally like bit-flips in a Gray code? (M Joonas Pihlaja)
xxx ("Sphere")
Re: software protection schemes (lament)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: small subgroups in Blum Blum Shub
Date: 18 Jun 2000 16:09:20 -0700
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> Sure. Very easy. Disproof by contrary example, or false case. All
> we need to find is one false case and the claim (that X^2 mod N is
> proven secure without short cycle checks) fails.
No, I think you misunderstood the claim.
You present a disproof of the (false) claim "there are no short cycles".
The post presents a proof of the (apparently true) claim
"if you select a starting point at random as given in the post, then
the chances of hitting a short cycle are negligible, assuming factoring
is hard". There is no contradiction here.
In other words, if you're going to worry that you choose a starting
point that begins on a short cycle, you might as well spend your time
worrying that the adversary gets lucky and guesses a prime factor of N.
(And we know that worrying about _that_ is a waste of time...)
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Subject: Re: small subgroups in Blum Blum Shub
Date: 18 Jun 2000 16:12:23 -0700
In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
> You attempt to make the issue the same as the usual key selection, but
> that is a false analogy. For most of our ciphers, key selection is
> arbitrary. But here, key selection is *not* arbitrary, because weak
> keys exist. So the enciphering end has the chance to screw things up
> by selecting a weak key, or to avoid that by checking first.
No, I'm not talking about key selection. This has nothing to do with
weak keys.
Whatever N the enciphering end chooses, there is a chance (albeit a very
small one!) that the attacker guesses a prime factor of N just by luck.
This is true _no matter how the enciphering end chooses N_.
You can never rule out the chance that the attacker gets lucky and guesses
your private key correctly. It's simply unavoidable.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
Date: Sun, 18 Jun 2000 23:19:07 GMT
On Sun, 18 Jun 2000 08:15:28 -0400, "G. A. Edgar"
<[EMAIL PROTECTED]> wrote, in part:
>There are no vowels in Sanscrit, so we cannot criticize you for this.
Well, although Sanskrit is a language not currently used, like Latin,
it is true that Hindi is written using the Devanagari writing system
as well.
However, the Devanagari writing system (and its relatives, such as the
methods by which Tibetan and Siamese are written) is not entirely
without vowels.
Although the number of symbols corresponds to the number of consonants
in the language - *plus one* - they are thought of as standing for
syllables, not consonants. Each one stands for the consonant followed
by the vowel a. The one additional symbol stands for no consonant -
still "preceding" the vowel a. Additional marks above or below the
symbol change it to another vowel: unlike vowel points in Hebrew,
which are not used routinely (only in books for children, or in
writing Scripture which must be protected against misreading), these
marks are routinely used in writing.
Thus, normal texts written in languages using scripts of the
Devanagari type do have unambiguous vowel indication.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Crossposted-To: sci.math
Subject: Re: AWFUL PUN (was: Why the golden ratio?)
Date: Sun, 18 Jun 2000 23:23:08 GMT
On Sun, 18 Jun 2000 09:20:06 -0600, [EMAIL PROTECTED] (wtshaw) wrote,
in part:
>In article <[EMAIL PROTECTED]>,
>[EMAIL PROTECTED] (John Savard) wrote:
>> Nobody commented on this awful pun? (As the mathematician in question
>> is deceased, I suppose he can't do anything but rest on his laurels.)
>Are we to curry f(l)ave(/o)r with such an observation?
No, as I'm talking about the British mathematician who was
instrumental in bringing Ramanujan to England, out of India. He had
written of how astounded he was at the formulas Ramanujan had composed
- "they had to be true, as no one would have had the imagination to
invent them".
I was hoping someone would get my *original* pun, which was what I
tried to call attention to (the reference to _laurels_ was simply an
easier clue to the name of W. H. Hardy) ... as W. H. Hardy is also the
author of a famous essay, "A Mathematician's Apology", where he
explains the relevance of pure mathematics as an activity.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: small subgroups in Blum Blum Shub
Date: 18 Jun 2000 23:44:36 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] (David A. Wagner) wrote:
>
> >Well, now I'm curious. What was wrong with the old article at
> >the URL above? It looked correct to me. What am I missing?
> >I'd love to hear a technical refutation, if there is one...
>
> Sure. Very easy. Disproof by contrary example, or false case. All
> we need to find is one false case and the claim (that X^2 mod N is
> proven secure without short cycle checks) fails.
Err... I thought that the BBS generator was secure given that factoring
the modulus is hard. I also thought that the article referred to showed
a way to factor the modulus easily given a short cycle, by finding a
pair of square roots of a quadratic residue. This (to my mind, at any
rate) violates the hypothesis that factoring the modulus is hard.
The argument given is that a similar cycling attack also works against
general RSA moduli, although nobody bothers choosing RSA moduli
carefully to avoid this attack because finding short cycles is too
difficult anyway. Since 1/4 of RSA moduli are Blum integers, a problem
with finding short cycles in Blum integers specifically would also
imperil a large class of RSA moduli.
-- [mdw]
------------------------------
From: "Lyalc" <[EMAIL PROTECTED]>
Subject: Re: Weight of Digital Signatures
Date: Mon, 19 Jun 2000 10:01:27 +1000
The subtext of many of the press reports is that 'equally binding' implies a
similar level of supporting infrastructure is required to allow relying
parties to have a similar level of confidence in the received data.
A single technology, on it's one, has never provided a secure solution, nor
a reliable one.
Lyal
Mok-Kong Shen wrote in message <[EMAIL PROTECTED]>...
>
>
>John Savard wrote:
>
>> I really don't know if this is good news.
>>
>> A law that makes a digital signature "just as binding as one in ink",
>> when it is so much easier to break into someone's house and read their
>> hard drive than forge their signature perfectly makes ordinary people
>> much more vulnerable to forgery than before.
>
>But if it is not equally binding, it, by definition, wouldn't be a
>signature. So how should one go about, if one wants to reap the
>benefits offered by electronics and decrease the frequency of
>signing in ink?
>
>M. K. Shen
>
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 00:09:03 GMT
On 18 Jun 2000 16:09:20 -0700, in
<8ijkr0$lss$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>> Sure. Very easy. Disproof by contrary example, or false case. All
>> we need to find is one false case and the claim (that X^2 mod N is
>> proven secure without short cycle checks) fails.
>
>No, I think you misunderstood the claim.
>
>You present a disproof of the (false) claim "there are no short cycles".
>The post presents a proof of the (apparently true) claim
>"if you select a starting point at random as given in the post, then
>the chances of hitting a short cycle are negligible, assuming factoring
>is hard". There is no contradiction here.
No. Here is the beginning issue:
>>>>>> >The nonsense about choosing "strong primes" or
>>>>>> >good initialization values is a remnant to the past where it was
>>>>>> >thought that a relatively small prime (if well chosen) would be
>>>>>> >adaquately strong.
The claim is absurd. The reason for the BB&S special primes
construction is to guarantee long cycles, and then select x0 on such a
cycle. All that is necessary to complete a proof of security. Proven
security is what the BB&S construction brings to the party, and why
one might use it. Note how the issue has just become "proven
security."
Then the issue is whether the BB&S construction is needed for proven
security. That is, the issue is whether X^2 mod N by itself -- absent
BB&S protocols -- is "proven secure." It is not, unless you think
"proof" is the same as "almost certainly." I don't.
>In other words, if you're going to worry that you choose a starting
>point that begins on a short cycle, you might as well spend your time
>worrying that the adversary gets lucky and guesses a prime factor of N.
>(And we know that worrying about _that_ is a waste of time...)
I don't worry about it at all. I have said repeatedly that this
discussion is not about practical security.
This discussion is about whether X^2 mod N is "proven secure." And
all that is necessary for X^2 mod N insecurity is for the encrypting
end to choose a wrong x0. That danger can be completely eliminated,
but if it is not, X^2 mod N, in practice, is not necessarily secure.
It is probably secure, almost surely secure, good enough secure, but
for all that is *not* "proven secure." And that is why the BB&S
article has all that stuff on the end that nobody ever reads.
---
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: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 00:16:36 GMT
On 18 Jun 2000 16:12:23 -0700, in
<8ijl0n$ltg$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (David A. Wagner) wrote:
>In article <[EMAIL PROTECTED]>, Terry Ritter <[EMAIL PROTECTED]> wrote:
>> You attempt to make the issue the same as the usual key selection, but
>> that is a false analogy. For most of our ciphers, key selection is
>> arbitrary. But here, key selection is *not* arbitrary, because weak
>> keys exist. So the enciphering end has the chance to screw things up
>> by selecting a weak key, or to avoid that by checking first.
>
>No, I'm not talking about key selection. This has nothing to do with
>weak keys.
Sure it does. Avoiding weakness in the keying is what BB&S brings to
the party, above and beyond X^2 mod N by itself. It is the reason for
the complex BB&S "special primes" construction.
>Whatever N the enciphering end chooses, there is a chance (albeit a very
>small one!) that the attacker guesses a prime factor of N just by luck.
>This is true _no matter how the enciphering end chooses N_.
But weak keys bring weakness *without* the attacker guessing. A weak
key (an X^2 mod N initial value on a short cycle) is selected by the
enciphering end, not the attacker. They are an *additional* weakness,
above and beyond the normal attacker guessing.
>You can never rule out the chance that the attacker gets lucky and guesses
>your private key correctly. It's simply unavoidable.
Fine, but the issue here is weakness *beyond* guessing the key. It is
the (theoretical) possibility that a stream cipher is using a
generator with a short cycle. It is the possibility that, having
deciphered only the short cycle, the attacker can now run that
repeating sequence through the end of the message without further
work.
---
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: small subgroups in Blum Blum Shub
Date: Mon, 19 Jun 2000 00:31:05 GMT
On 18 Jun 2000 23:44:36 GMT, in <[EMAIL PROTECTED]>, in
sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>[...]
>Err... I thought that the BBS generator was secure given that factoring
>the modulus is hard. I also thought that the article referred to showed
>a way to factor the modulus easily given a short cycle, by finding a
>pair of square roots of a quadratic residue. This (to my mind, at any
>rate) violates the hypothesis that factoring the modulus is hard.
Quite right. If we start out by *assuming* security, we are quite
unlikely to be able to get any lesser results. Surely this is a wrong
mathematical construction to use if we are interested in finding
insecurity. The correct conclusion to be drawn from the demonstration
is that the assumption is false *under* *particular* *circumstances*,
in particular, when a short cycle is used.
>The argument given is that a similar cycling attack also works against
>general RSA moduli, although nobody bothers choosing RSA moduli
>carefully to avoid this attack because finding short cycles is too
>difficult anyway. Since 1/4 of RSA moduli are Blum integers, a problem
>with finding short cycles in Blum integers specifically would also
>imperil a large class of RSA moduli.
Again right. But RSA is a practical system. In practice, the
probability of choosing a short cycle is very, very low. The issue,
however, from the time I came into the construction, was something
like "why would anyone use the complex special primes BB&S
construction":
>>>>>> >The nonsense about choosing "strong primes" or
>>>>>> >good initialization values is a remnant to the past where it was
>>>>>> >thought that a relatively small prime (if well chosen) would be
>>>>>> >adaquately strong.
And that is nonsense. The BB&S construction brings something to the
party which plain X^2 mod N does not, and that is the recipe for
assuring that a short cycle is not chosen. This is not, as far as I
know, a practical issue. Instead, this is an issue of *proof*: the
ability to claim to be using a system with "proven security." Such a
claim requires that short cycles be avoided somehow, for short cycles
surely exist, and if a short cycle *is* selected, the system is
unarguably insecure. *That* is the reason for the complex "special
primes" BB&S construction.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Q: Equally like bit-flips in a Gray code?
Reply-To: [EMAIL PROTECTED]
Date: Sun, 18 Jun 2000 23:57:21 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: M Joonas Pihlaja wrote:
:> I'm trying to find a Gray code in which each bit is 'equally
:> likely' to change between adjacent code words. Well, more likely
:> than in the the usual (ix+1)^(ix>>1) code at least. That changes
:> the lower k bits before it gets to bit k.
: I doubt that you would get a solution. [...]
There's an exact solution for a two-bit Gray code:
0 - 00 1 - 01 2 - 11 3 - 10
I'd also be sceptical in the more general case.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Equally like bit-flips in a Gray code?
Date: Sun, 18 Jun 2000 17:24:54 -0700
M Joonas Pihlaja <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I hope this is the appropriate forum for this type of question.
>
> Hi,
>
> I'm trying to find a Gray code in which each bit is 'equally
> likely' to change between adjacent code words. Well, more likely
> than in the the usual (ix+1)^(ix>>1) code at least. That changes
> the lower k bits before it gets to bit k.
Of course, if the cipher is such that some bits are easier to change than
others, you can take advantage of that in a Gray code -- use a bit
permutation to move all the LSBits of the Gray code to the bits that you
don't mind changing...
>
> I need to uniformly sample the key space of a cipher and was
> going to use a Sobolev sequence, but noticed that a Gray code
> would allow for some optimisations.
It's been a while since I read the paper, but (IIRC) this addresses
precisely what you asked:
M. Schwartz and T. Etzion, "The Structure of Single-Track Gray Codes"
IEEE Transactions on Information Theory, November 1999, pg 2383-2396
--
poncho
------------------------------
From: M Joonas Pihlaja <[EMAIL PROTECTED]>
Subject: Re: Equally like bit-flips in a Gray code?
Date: Mon, 19 Jun 2000 04:53:39 +0300
On Sun, 18 Jun 2000, Scott Fluhrer wrote:
> Of course, if the cipher is such that some bits are easier to
> change than others, you can take advantage of that in a Gray
> code -- use a bit permutation to move all the LSBits of the
> Gray code to the bits that you don't mind changing...
Yes, that was my plan. First find the key bits that affect the
cipher bits the least (or most). Ideally there should be a 50/50
chance of a given cipher bit changing when you flip a given key
bit, but if that probability is much less than 0.5 then the key
bit doesn't matter as much (and can be disregarded). OTOH, if
the probability is close to 1, then it's a good key bit to choose
for Gaussian elimination.
The first step is sampling the cipher's key space to find those
naughty key bits, and with a Gray code you can test each key bit
as it changes.
> It's been a while since I read the paper, but (IIRC) this addresses
> precisely what you asked:
>
> M. Schwartz and T. Etzion, "The Structure of Single-Track Gray Codes"
> IEEE Transactions on Information Theory, November 1999, pg 2383-2396
Thanks, I finally have something to fetch from the library. I
also found:
Bhat, Girish S. and Savage, Carla D., "Balanced Gray Codes",
Electronic Journal of Combinatorics 3, No. 1, R25 (1996)
available from:
http://www.csc.ncsu.edu/faculty/savage/papers.html
It contains an existence proof for balanced n-bit Gray codes.
Thanks again,
Joonas
------------------------------
From: "Sphere" <[EMAIL PROTECTED]>
Subject: xxx
Date: Sun, 18 Jun 2000 23:11:09 -0300
------------------------------
From: lament <[EMAIL PROTECTED]>
Subject: Re: software protection schemes
Date: Mon, 19 Jun 2000 02:27:33 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> RecilS wrote:
> > They don't all currently suck. All mass-market schemes suck simply because
> > they do not have the time to tailor computer-specific protection. An actual
> > recompilation of source (not a key-code algorithm) which relies upon the
> > processor's ID to decrypt necissary code seems to work for me.
>
> Why ? You simply replace the assembly code which gets that "unique" id
> with a routine which returns that unique id - then your "perfect"
> protection is also broken.
Good point. But what if the "code which gets the unique ID" returns a hashed version
of the found ID? This hashed value is saved in "global" memory, and is operated on at
various times by various pieces of code in the application, especially during
startup. Each operation further hashes/changes the global value until -- sometime
later -- it is used. The "sometime later" may only be a second or two -- but that's a
lot of code to step through with a debugger. The "is used" means that the current
value is used in a calculation or other operation such that if the value is
incorrect, the program will fail.
A simple example is that a current value is the limit in a FOR loop, or is bitwise
ANDed to a local integer. Subsequent changes are made to the value, and usages occur
during the normal execution of the program. All subsequent values, or most all, have
to be correct. A value could be accessed many times (in a loop) in a harmless way,
but would cause a debugger to repeatedly detect a "hit." Further, a single hashed
value can be replicated into many other hashed global values at various times and
places in the application. Some are used in an essential way, some not. I think it
would be very difficult to hunt down all accesses to this data, and determine what
the initial "returned ID' ought to be.
------------------------------
** 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
******************************
