Cryptography-Digest Digest #457, Volume #12 Wed, 16 Aug 00 07:13:00 EDT
Contents:
IDEA Test Vectors ("Sam Simpson")
Re: OTP using BBS generator? (Mark Wooding)
Re: OTP using BBS generator? (Mark Wooding)
Re: Crypticon novel book (Mark Wooding)
Re: 215 Hz five-qubit quantum processor (Tim Shoppa)
Re: IDEA Test Vectors (Mark Wooding)
Re: 1-time pad is not secure... (Tim Tyler)
Re: 1-time pad is not secure... (Tim Tyler)
Re: 1-time pad is not secure... (Tim Tyler)
Re: 215 Hz five-qubit quantum processor (Nick Maclaren)
Re: OTP using BBS generator? (John Savard)
Re: www.curious.4ears (John Wasser)
Re: 1-time pad is not secure... (Tim Tyler)
Re: 1-time pad is not secure... (Tim Tyler)
Re: xor confusion! (John Wasser)
----------------------------------------------------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: IDEA Test Vectors
Date: Wed, 16 Aug 2000 10:22:07 +0100
Just an observation really, I'm sure people have seen this before,
but:
Key, Plaintext, Ciphertext
00000000 00000000 00000000 00000000, 00000000 00000000, 01000100
00000000
00000000 00000000 00000000 00000000, 00000000 00000001, 01000144
00380093
00000000 00000000 00000000 00000000, 00000000 00000010, 01000140
00800030
00000000 00000000 00000000 00000000, 00000000 00000011, 012001e4
00780043
Is my test code funky, or does the above seem a little "regular". I
assume these are related to the weak keys as outline AC2 pg 323.
Very disconcerting when testing coding :)
--
Sam Simpson
Comms Analyst
http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
Delphi Crypto Components. PGP Keys available at the same site.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 16 Aug 2000 09:42:26 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> These facts, together with David Hopwood's information that BBS left
> 'explicitly' open the question of the relationship between the said
> two types of cycles lengths, seem to sufficiently justify the
> conjecture that there is somewhere a theory GAP in BBS's proof of
> security, in my guess probably on the path from the difficulty of
> predicting the direct output to the congruence relation to the
> difficulty of predicting the LSB. (There is, as far I am aware, NO
> clear-cut and useful relationship between these two types of entities
> in general!)
There is a useful relationship between the two types. Note that the
period length of the parity sequence must be a factor of the period
length of the <x_i> sequence.
A thought has struck me. Please stop me if it turns out to be hopelessy
wrong. If it isn't, it will (a) sort out the parity sequence period,
and (b) reduce the effort required to find BBS moduli with long periods.
I can't believe that nobody's trodden this ground before: my abilities
as a number theorist are somewhat limited.
My inspiration is the work of Lim and Lee on attacking discrete log
systems over GF(p).
\newcommand{\pimax}{\pi_{\mathrm{max}}}
The <x_i> period, usually notated as \pi, we know to be a factor of
\pimax = \lambda(\lambda(n)) = \lambda(\lcm(p - 1, q - 1)).
Let p = 2 p_0 p_1 p_2 ... p_k + 1 and q = 2 q_0 q_1 q_2 ... q_l + 1 be
two prime numbers, where the p_i and q_i are primes greater than some
given threshold t_0. Primes of such a form can be found fairly readily,
by constructing a pool of smaller primes and analysing the products of
all appropriately sized combinations, as described in Lim and Lee's
paper. Then \lcm(p - 1, q - 1) = 2 p_0 p_1 p_2 ... p_k q_0 q_1 q_2
... q_l.
Going down another level, choose each of the p_i and q_i to be
Sophie-Germain or Lim-Lee primes as well (depending on how small your
numbers are by this point): ensure that each p_i has the form 2 \prod
r_i + 1, where the r_i are all greater than some threshold t_1.
We end up in the situation that \pimax is twice the product of a number
of primes whose minimum size is strictly greater than our bound t_1. We
know that the period \pi any *parity* sequence must be a factor of
\pimax. But the only small prime factor of \pimax is 2, and we can
easily check for periods of length 2. By choosing t_1 = 2^{128}, for
example, we can ensure that a cycle found either has period 2 or longer
than 2^{128}, which is obviously impractical to traverse.
I still think it's a waste of time trying, by the way. I'm just trying
to clarify the field a little.
> This issue is evidently EXTREMELY important, for otherwise the
> 'provably security' of BBS would have been a simple FICTION!
No. You've misunderstood the proof almost completely.
> I like to take this opportunity to once again point out the importance
> of experimentally checking the statistical properties of the LSB of
> BBS, in ways EXACTLY as every other PRNG ever used in practice has
> been checked.
> (What qualifies BBS to be an 'exception' in this??)
The fact that breaking it is reducible to factoring the modulus.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: OTP using BBS generator?
Date: 16 Aug 2000 09:52:14 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> My problem is in knowing the (rough) path of attaining that knowledge,
> without having to deeply study the BBS article which I guess is way
> beyond my capability. My thought is this: BBS must proceed from the
> properties of the congruence relation to that of the LSB. They
> presumably could have first established that finding cycles of the
> direct output of the congruence relation is no easier than factoring.
The BBS paper establishes the reduction to the quadratic residuosity
problem only, not to factoring. The reduction to factoring was done
afterwards by Vazirani and Vazirani (Crypto '84, I think).
> Since there is a gap in proceeding from the cycles of this kind to the
> cycles of LSB, I conjecture there could be some difficulties of
> continuing from the above point to establish that finding cycles of
> LSB is no easier than factoring.
>
> Looking from another perspective, what does 'finding cycles in LSB'
> mean? If the distribution of cycles lengths of LSB is (of course I
> don't know) is such that the majority of cycles are very short, then
> encountering a cycle would be easy. So I conjecture that one has to be
> able to say something definite about the distribution of cycle lengths
> of LSB, if one can prove that finding cycles of the LSB is no easier
> than factoring.
No. The proof is much more general than that. It shows that *any*
method of predicting the generator's output allows you to factor.
[There is no `gap'.]
> Why is it then, as David Hopwood said, that BBS leave the issue of the
> connection between the cycles of the direct output of the congruence
> relation and the cycles of LSB explicitly to be an open question? I
> surmise that that gap or open question must have some non-trivial
> bearing on the present issue.
Not really. The actual cycle analysis is interesting but fundamentally
unimportant. (Although see my other article which shows how to obtain a
lower bound on parity cycle lengths and generate moduli without the
expense of finding the `special' numbers.)
The analysis of cycle lengths and distributions is *independent* of the
proof that prediction of the generator is as hard as factoring.
> If a bit sequence has grave statistical defects, then that can be
> readily exploited by the opponent, he wouldn't then need any
> 'polynomial' time or what not for doing the analysis. Or am I missing
> something?
Hence the proof shows that *either* factoring is surprisingly easy *or*
a BBS generator has no such defects. In your toy examples, factoring is
too easy.
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Crypticon novel book
Date: 16 Aug 2000 09:54:55 GMT
DEXMilano <[EMAIL PROTECTED]> wrote:
> I've seen news about a novel (I don't remember the Uathor) named
> Crypticon. Is there anyone read it? Comments?
It's called `Cryptonomicon', it's by Neal Stephenson, and it's rather
good.
-- [mdw]
------------------------------
Date: Wed, 16 Aug 2000 06:09:43 -0400
From: Tim Shoppa <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
David T. Wang wrote:
> IMO, the "golden days" of computer architects and engineers are gone.
> The world doesn't revolve around fast processors anymore. The focus
> has been shifting ever so slowly from concentrating on how to perform
^^^^^^
> computations quickly to figuring out how to move the data really fast
> from point A to point B.
Slowly? Haven't we been at this point since we had sub-nanosecond
ECL in the 1970's?
I suspect you're really talking about what I call "Desktop computing".
> In that train of thought, even if IBM announced
> a "128 bit quantum computer", I would most likely just keep my head
> buried and continue to pound away at my keyboard. If however, someone
> figures out a clever way to "setup the quantum state" in a few seconds
> (or ns, or minutes.. Just not years) and subseqently receive the result
> of the computation in an equally short and reasonable amount of time,
> then I would really sit up and take notes. This "secondary" development
> on this technology, although not as glamourous to the general public,
> would instantly grab my attention, because that would mean that there
> is a way I can actually take advantage of this technology, and not just
> as a scientific curiosity.
I don't think we'd have to get to the "128 bit quantum computer"
to get that far. My understanding is that the "power" of a quantum
computer goes like the factorial of the number of qubits, and
20! is a *very* big number.
Of course, none of this will ever help run Linux or Microsoft Windows,
so you're right, this is such a fundamental change in computation
that it won't matter except to those who are already computing off
the desktop.
Tim.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: IDEA Test Vectors
Date: 16 Aug 2000 10:10:18 GMT
Sam Simpson <[EMAIL PROTECTED]> wrote:
> Just an observation really, I'm sure people have seen this before,
> but:
>
> Key, Plaintext, Ciphertext
> 00000000 00000000 00000000 00000000, 00000000 00000000, 01000100
> 00000000
> 00000000 00000000 00000000 00000000, 00000000 00000001, 01000144
> 00380093
> 00000000 00000000 00000000 00000000, 00000000 00000010, 01000140
> 00800030
> 00000000 00000000 00000000 00000000, 00000000 00000011, 012001e4
> 00780043
>
>
> Is my test code funky, or does the above seem a little "regular". I
> assume these are related to the weak keys as outline AC2 pg 323.
That looks about right.
IDEA has two undesirable key schedule properties:
* It uses key bits directly from the user key. It divvies the user
key into 16-bit chunks, uses them all, then rotates the entire user
key by 25 bits and repeats. If the user key is zero, all subkeys
will be zero.
* The strongly nonlinear operation, multiplication in GF(2^{16} + 1),
is always performed between a text word and a subkey word. The zero
word from the key is mapped to -1 in the field, so the effect of the
multiplication is to replace an input x by 1 - x mod 2^{16}.
The fact that addition is also only done between (zero) key words and
text words, and is therefore a no-op in this case, is just icing on the
cake.
Anyway, the result is that, with zero keys, IDEA's diffusion becomes
rather bad.
> Very disconcerting when testing coding :)
Agreed. ;-)
-- [mdw]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 Aug 2000 09:58:47 GMT
Tony T. Warnock <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> As far as physics goes, science does not appear to be in any sort of
:> position to make proclamations on the issue of whether true randomness
:> exists. The issue relates to issues on the very edge of theoretical
:> physics - an area where not everything is known. The issue could easily
:> go either way on some distant future occasion.
: Is this a 50-50 proposition?
I have no idea.
All I know is that it's not a 100-0 proposition, by any stretch of the
imagination.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 Aug 2000 10:10:39 GMT
Mark T. VandeWettering <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:>Any process that appears random may be the deterministic outcome of events
:>at a lower level. The rational scientist can't currently say one way or
:>the other about whether there is determinism in physics - he plain doesn't
:>know.
: Quantum mechanics addresses this issue. It disagrees with you. Please
: post your refutation of quantum mechanics [...]
Quantum mechanics does not address the issue - to do so it would have to
claim to be a final theory of physics - something which - AFAIK - no
living physicist would claim for it.
*If* Heisenberg's uncertainty priciple were the last word ever spoken on
the matter it might be reasonable to conclude that it's not possible to
gain enough information about the state of the universe to predict it.
However, as things stand there's still plenty of scope for discovering
more physics which underpins it.
People might have thought that Brownian motion was random before the
kinetic theory of gasses offered a more detailed explanation. It may
well be similar with quantum theory.
Certain types of determinism have been experimentally revealed to be
very unlikely - but not all such theories can be rejected at present.
I don't "disagree" with quantum mechanics - unless it is presented as the
final theory of the universe - which it is /extremely/ unlikely to be.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 Aug 2000 10:17:59 GMT
Guy Macon <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:>Except that it doesn't say any such thing. Completely deterministic
:>interpretations of quantum theory exist, namely - for example - the MWI.
:>
:>Such interpretations make no use of random events - and are consistent
:>with all observations to date.
: Not suprising, considering that the MWI predicts that your experiments
: will give you the exact same answers as you would have recieved if
: randomness exists.
Indeed.
Incidentally, to veer further off topic for a moment, this doesn't mean
the various interpretations are indistinguishable from one another.
MWI and CI disagree (I believe) over issues where "observers" are
interfered with one another. MWI allows observers to be in a
super-position of states, while the CI (presumably) does not.
Since observers are typically large objects, distinguishing between the
theories experimentally will not be easy, and Occam's rasor and parsimony
should probably be applied instead.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: [EMAIL PROTECTED] (Nick Maclaren)
Crossposted-To: comp.arch
Subject: Re: 215 Hz five-qubit quantum processor
Date: 16 Aug 2000 10:37:58 GMT
In article <[EMAIL PROTECTED]>, Tim Shoppa
<[EMAIL PROTECTED]> writes:
|> David T. Wang wrote:
|> > IMO, the "golden days" of computer architects and engineers are gone.
|> > The world doesn't revolve around fast processors anymore. The focus
|> > has been shifting ever so slowly from concentrating on how to perform
|> ^^^^^^
|> > computations quickly to figuring out how to move the data really fast
|> > from point A to point B.
|>
|> Slowly? Haven't we been at this point since we had sub-nanosecond
|> ECL in the 1970's?
No. I can assure you that the people who were saying that in the
late 1970s were prophets crying in the wilderness. Furthermore,
even in the late 1980s, many CPU designers were still thinking in
terms of MIPS and MFlops - this was true of marketdroids and the
people holding the moneybags for a decade beyond that, and to a
certain extend still is.
|> I don't think we'd have to get to the "128 bit quantum computer"
|> to get that far. My understanding is that the "power" of a quantum
|> computer goes like the factorial of the number of qubits, and
|> 20! is a *very* big number.
Only if it solves a problem that you are interested in. I am not
fully up with the field, but I don't think that even 1,000 128-bit
quantum computers will help when factorising a 256-bit number. You
really do need a 256-bit quantum computer for a 256-bit problem.
Factorising 20-bit numbers very fast isn't a major requirement :-)
Regards,
Nick Maclaren,
University of Cambridge Computing Service,
New Museums Site, Pembroke Street, Cambridge CB2 3QG, England.
Email: [EMAIL PROTECTED]
Tel.: +44 1223 334761 Fax: +44 1223 334679
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: OTP using BBS generator?
Date: Wed, 16 Aug 2000 10:48:07 GMT
On Wed, 16 Aug 2000 10:32:33 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>John Savard wrote:
>> On 15 Aug 2000 16:54:32 GMT, [EMAIL PROTECTED] (Mark Wooding) wrote, in
>> part:
>> >Terry Ritter <[EMAIL PROTECTED]> wrote:
>> >> That's a wrong answer: The construction as described in BB&S first
>> >> guarantees that cycles of a given length must exist, and then shows
>> >> how to check that x0 is on such a cycle. The check is thus absolute
>> >> proof that a short cycle has not been selected.
>> >No, it only shows the cycle length for the sequence <x_i>, not the
>> >sequence of parity bits.
>> Since the BBS modulus can't be a power of two, I don't think you have
>> to worry about that.
>Do I understand correctly that you claim that the cycle
>length of <x_i> equals the cycle length of the parity bits
>(either the normal definition or LSB)? Thanks.
I believe I do, or at least I make a weaker claim that still shows the
cycle length of the parity bits has to be long.
Essentially, since the modulus is the product of odd primes or an odd
prime, or something like that,
and the parity bit has two possible values,
and the seed is not allowed to be zero,
it follows that certain cycle lengths are not possible. Now, if the
cycle length for the generator as a whole is pq, for p and q prime,
proving that the parity bit can't have a cycle length of p or a cycle
length of q would require advanced math, it IS clear that no other
cycle length for the parity bit less than pq is possible.
That the parity bit will be unbiased would also require advanced math
to show, but since it's been proven "hard to predict", that would
imply that such a proof does exist.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Subject: Re: www.curious.4ears
From: John Wasser <[EMAIL PROTECTED]>
Date: Wed, 16 Aug 2000 11:03:32 GMT
[[ This message was both posted and mailed. ]]
In article <8kaubj$28e$[EMAIL PROTECTED]>, rosi <[EMAIL PROTECTED]> wrote:
> I sincerely hope some kind people who can get in touch with Andrew
> Odlyzko of AT&T may kindly help me solve (or partially solve) the www
> puzzle:
> Where did my e-mail messages to Andrew go?
Where did you send them?
Did you use the contact information on his AT&T webpage:
http://www.research.att.com/~amo/
Contact information:
Address: Andrew M. Odlyzko
AT&T Labs - Research
Room C225
180 Park Ave., Bldg. 103
P.O. Box 971
Florham Park, NJ 07932-0971
USA
Phone: 973 360 8410
Fax: 973 360 8178
URL: http://www.research.att.com/~amo
Email: [EMAIL PROTECTED]
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 Aug 2000 10:41:21 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> Any process that appears random may be the deterministic outcome of
:> events at a lower level.
: Definitely wrong when applied to quantum phenomena.
Definitely wrong. The world /could/ exist entirely as a simulation
in God's deterministic computer. It would then be *entirely* the
deterministic outcome of events at a lower level.
If you want a deterministic theory of physics, see (for example):
Digital physics: http://cvm.msu.edu/~dobrzele/dp/
Alternatively, look up Ed Fredkin's 1990, "Digial Mechanics" paper.
Fredkin deals explicitly with the notion that supposed quantum
randomness is incompatible with a lower level of determinism.
:> If randomness in physics /were/ as well established as the law of
:> gravity, there would be less discussion about its existence.
: Actually the fundamental randomness is better established than any
: theory of gravitation.
Again, we don't agree. Gravitation may be superceeded by more precise
theories, but these are still likely to make much the same predictions.
If quantum theory is revised, no doubt its replacement will make very
similar predictions as well, but the common view of the existence - or
otherwise - of fundamental physical randomness may be *totally reversed*
by future discoveries.
:> : And in fact there *are* random bitstream generators based
:> : on fundamentally random physical processes.
:>
:> Indeed. However, nobody really knows how close to perfect
:> randomness the results of such generators get.
: By what measure? It is hardly a valid criticism of a design
: to say that it doesn't meet some unmeasurable criterion.
With tests, you can conclude that non-randomness exists, but never
that true randomness does, since that would suggest that every
conceivable test for randomness has been passed.
This means that you can't legitimately claim a source is truely
random on the basis of testing it, since you've got no way to
know for certain.
That you can't test for perfect randomness doesn't mean that you should
by default award today's hardware generators the acolade of "truely
random".
Rather, the reverse - you should *not* make that statement, since you have
no basis for making it.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: 1-time pad is not secure...
Reply-To: [EMAIL PROTECTED]
Date: Wed, 16 Aug 2000 10:46:57 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
: Tim Tyler wrote:
:> That appears to be a huge overstatement. Yes, certain local hidden
:> variable theories have been discounted... but it's plain false to say
:> that *any* hidden variables that might "exist" *must* produce exactly
:> the same effects as true randomness [emphasis added].
: No, *all* local hidden variable theories have been ruled out.
: So far from being an overstatement, it was a summary of the
: best current knowledge resulting from controlled experiment.
You wrote:
``The current state of our knowledge about this is that any hidden
variables that might "exist" must produce exactly the same effects
as true randomness.''
That was wrong. Hidden variables /may/ exist, they just can't have
wholly local effects.
You made this statement about [I quote, but add emphasis] "*any* hidden
variables" - not any purely *local* hidden variables.
That statement was false. It was an overstatement - not a summary of
what's currently known.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
Subject: Re: xor confusion!
From: John Wasser <[EMAIL PROTECTED]>
Date: Wed, 16 Aug 2000 11:09:50 GMT
[[ This message was both posted and mailed. ]]
In article <8kt1qf$b29$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]>
wrote:
> Thanks! I didn't understand that XOR was a bitwise operation, and from
> the different results I got, I thought that you added the numbers or
> something. Guess not!
It actually IS a form of adding the numbers. The XOR is the same as
adding the numbers if you throw away the carry from each bit.
0+0=0
0+1=1
1+0=1
1+1=0 (with a carry of 1 which we ignore)
XOR is also sometimes called "modulo 2 addition".
------------------------------
** 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
******************************
