Cryptography-Digest Digest #405, Volume #12 Thu, 10 Aug 00 22:13:01 EDT
Contents:
Re: Random Number Generator ("Scott Fluhrer")
Re: EGD based on Yarrow for Windows?? (Ian Upright)
Re: 1-time pad is not secure... ([EMAIL PROTECTED])
Re: Pentium III h/w RNG ("Joseph Ashwood")
Re: OTP using BBS generator? (lcs Mixmaster Remailer)
Re: 1-time pad is not secure... ([EMAIL PROTECTED])
Re: chap authentication scheme? (Bill Unruh)
Re: The quick brown fox... (John Savard)
Re: Best AES candidates ?? Slow Skipjack might have advantage (John Savard)
Re: Interesting new Rijndael paper by Robshaw & Murphy: (Scott Contini)
Re: OTP using BBS generator? (David Hopwood)
Re: OTP using BBS generator? (David Hopwood)
----------------------------------------------------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Random Number Generator
Date: Thu, 10 Aug 2000 17:28:58 -0700
<[EMAIL PROTECTED]> wrote in message news:8mtu40$9ck$[EMAIL PROTECTED]...
> Alex Random Number Generator
>
> The objective of this algorithm is to map finite
> key/seed to an infinite sequence of random bytes.
> The implementation has following characteristics:
>
> - 16 byte Key/Seed
> - 57% Avalanche Effect
> - 760Kbyte/sec performance
> - 64 Kbyte generated random string shows Null ZIP
> compression
> - The probability to find in random sequence 0/1
> value bits is exactly 50%
I looked at the algorithm, and it's dreadful. It basicly works by having 32
bytes of internal states, and going through these steps:
- An "arithmetic operation" that replaces various bytes within the state
with sums and products of the original values (mod 256). I suspect this may
be weak, but it is not the source of the problem.
- A "reflection operation", which throws away half the state, and replaces
it with the complement of the other half.
- A "permutation operation", which does a fixed permutation on the bits of
the state.
- At this point, you output all of the state as a 32 byte block
Obvious problems:
- This is not a CSRNG. Since there is no hidden state and no key dependance
on the operation, the second 32 byte block is a publicly computable function
of the first 32 byte block.
- The reflection operation enforces that exactly 128 bits of the block is 0
and 128 bits is 1. The permutation operation does not change this. This
means that each 32 byte block will have exactly 128 0's and 128 1's.
Obviously, real random sequences don't do this.
- Even worse, since the permutation operation is fixed, any linear
relationships generated by the reflection operation will appear at
predictable places in the output. For example, immediately after the
reflection operation, bit 0 of byte 0 is the complement of bit 0 of byte 1.
The permutation operation moves bit 0 of byte 0 to bit 5 of byte 5, and bit
0 of byte 1 to bit 3 of byte 12 (decimal). And so, in each block of the
output, bit 5 of byte 5 will always be the complement of bit 3 of byte 12 --
know one and you immediately know the other.
Other comments:
- The documentation of the algorithm was hideous (in no way could you
reconstruct the algorithm from that), and the only detailed description was
the source, which was mostly x86 assembly. This is ridiculous.
- If I wasn't worried about the above weakness, another thing I would worry
about is that the above operation throws away a *lot* of entropy. The
reflection operation itself throws away 128 bits each iteration, and the
arithmetic operation may throw away a considerable amount itself.
--
poncho
------------------------------
From: Ian Upright <[EMAIL PROTECTED]>
Subject: Re: EGD based on Yarrow for Windows??
Reply-To: [EMAIL PROTECTED]
Date: Fri, 11 Aug 2000 00:49:19 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>Ian Upright wrote:
>> I'm looking for an Entropy Gathering Daemon ...
>
>http://www.lothar.com/tech/crypto/
Ok, how about something written in C and is not perl based, and includes
sourcecode
Ian
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 00:43:45 GMT
40 messages in the thread within 16 hours! I am truely STUNNED! :)
I'm surprised that people brought up Chaos Theory because it just
reassures my point. If our world is chaotic, there's no such thing as
pure randomness. Every event will fall on "the 2-spiral" in a larger
scope. So it's like computing 1/x, we're chasing the impossible zero
with increasing computational power. OTP is only computationally
secure.
And here's my original conclusion that nobody commented on. Since the
key is not random, if someone attacks the scheme at the key generation
level, OTP is the LEAST secure because of its enormous key length.
Well, just imagine encrypting the Netscape 4.74 installation file,
19Megabytes. The key has 160,000,000 binary digits. That's like
010101100..............................................................
.......................................................................
Oh Boy! If you can only guess some small key patches with some
certainty, there are 160,000,000 places for you to try them out!
Let me try to solve this one:
1, 4, 18, 23, 0, 7, X. What is 'X'?
A 2-digit number with 90% certainty. Between 10-40 with 80% certainty.
If the list is much longer, more characteristics will emerge like this
individual doesn't pick 5 or 9 as often...
--Sisi
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Pentium III h/w RNG
Date: Thu, 10 Aug 2000 17:51:27 -0700
I think we all kind of gave up when it was discovered that if it wasn't
present the motherboard gave back random garbage. Actually some analysis was
done, but the only stuff I'm aware of was funded by Intel.
Joe
"David C. Barber" <[EMAIL PROTECTED]> wrote in message
news:8mvi5a$207f$[EMAIL PROTECTED]...
> The Pentium III is supposed to have some RNG function in it. A couple
times
> I'd heard that some analysis would be done with it, and even if it was
less
> than perfect, that that could be "fixed" with proper use. In the end, I
> never saw any analysis, though I'm sure some must have been done. Anyone
> have information and/or pointers on how well this function works?
>
> *David Barber*
>
>
>
------------------------------
Date: 11 Aug 2000 01:00:14 -0000
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Terry Ritter writes:
> It is *not* difficult to factor N . . . if we give a factor away. To
> even attempt to assume that factoring is difficult *implies* that the
> system be constructed in such a way as to not give away the secret.
> And a proper construction happens with BB&S (as far as I know), only
> when short cycles are excluded from use.
You are mixing up two things: the difficulty of factoring, and the
proper construction of the BBS RNG.
Factoring difficulty depends only on the choice of the factors.
Nothing you do after that will affect how hard it is to factor them.
Consider two RSA creators. One chooses an RSA modulus and lets the
attacker try to factor it. The other chooses an RSA modulus and then
sends random large integers to the attacker, which the attacker may
use to try to help him with factoring.
It should be clear that the second system is not any weaker than the
first one. It cannot leak any information about the RSA factors merely
by sending random data. If it could, then the first system's attacker
could achieve the same strength simply by using a source of random values
to aid its efforts.
In particular, there is no reason for the second system to filter or
check the random values that it sends in any way. Since these values
cannot aid the attacker, there is no reason to worry that one of them
may happen to reveal a factor of the RSA modulus. If circumstances
were such that that could happen, the attacker could find the same
information himself by running his own RNG.
The second system, without any checks, still has security equal to that
of the first. Its security is that of factoring an RSA modulus.
The second system is very similar to the BBS RNG, in that we choose an RSA
modulus and then we choose an independent random value to be the seed.
Terry Ritter is worried that this seed could lead to a short cycle.
It has been proven that if this happens, the RSA modulus could be
factored.
Therefore, if checking seeds to avoid those that lead to factorization
is necessary, as Terry Ritter argues, it follows that in the second
system above, it is also necessary to check the random values which are
sent in order to make sure that none of them could lead to factors.
The information which is being revealed in each case as the same effect.
Since we've already established that no such checking is necessary for the
second RSA system, it follows that no such checking is necessary for BBS.
BBS has all the security of the factoring problem, even when its seeds
are not checked for any special properties. They only have to be randomly
chosen. This is what is proven in BBS and the subsequent literature.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: 1-time pad is not secure...
Date: Fri, 11 Aug 2000 01:00:28 GMT
Well I made a big typo in my last message, so I cancelled it and
reposted. Now it's in an even bigger mess. Sorry about that.
In article <OEwOLsyAAHA.138@cpmsnbbsa08>,
"Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
> Actually the more important theory that was brought up was quantum
theory
> where we do have information that indicates that unless you can
predict the
> future you can't predict the future of the bit-stream.
Believe it or not, I think we can predict the future. :) Not everything
of course, but something. Like predicting the US stock market will go
down because Greenspan has raised interest rates to slow economic
growth. But more importantly, science and technology advances rapidly.
What seems impossible now will be possible to your grandchildren. So
you think nothing can go faster than light? Well keeping watching...
> > And here's my original conclusion that nobody commented on. Since
the
> > key is random, if someone attacks the scheme at the key generation
> > level, OTP is the LEAST secure because of its enormous key length.
> > Well, just imagine encrypting the Netscape 4.74 installation file,
> > 19Megabytes. The key has 160,000,000 binary digits. That's like
> >
010101100..............................................................
> >
.......................................................................
> > Oh Boy! If you can only guess some small key patches with some
> > certainty, there are 160,000,000 places for you to try them out!
>
> But how do you verify it? Let's make it a bit more real. If I encrypt
a
> plaintext P with 3DES, there exists a (XOR)OTP that will generate the
> plaintext (because under OTP all possible ciphertexts are possible,
and 3DES
> must generate a subset of that). How would you begin to generate that
pad?
> Of course you have only 1/(2^64) possible values to guess, so please
feel
> free.
Well lets say it wasn't an executable file but a long series of love
letters between a Canadian and a British spy in ascii. Then you'll get
meaningful plaintext if you get the right key patch at the right spot.
> > Let me try to solve this one:
> > 1, 4, 18, 23, 0, 7, X. What is 'X'?
> > A 2-digit number with 90% certainty. Between 10-40 with 80%
certainty.
> > If the list is much longer, more characteristics will emerge like
this
> > individual doesn't pick 5 or 9 as often...
> Except that is he is using a OTP usable RNG, than all numbers in the
output
> range are equally probable so 5 and 9 will occur with equal
likelihood to
> all other numbers. So lets put some reasonable restrictions on it,
say the
> maximum value is 31. Then the likelihood of a double digit number
showing up
> next would be 21/32. But the likelihood of guessing the value will be
1/32,
> regardless of the level of knowledge you have about the system. Your
> observations are actually the reason for the requirement that given
symbols
> 0-(n-1) and (n+1)-inf the symbol at n can be determined with no
likelihood
> above 1/(number of symbols), for all n. If you can prove or disprove
the
> existance of such a system I'd certainly be intersted in seeing it.
Of
> course there have been proofs that make progress, for example
Kosmogrov
> proved that you cannot determine whether or not a stream is truly
random
> based on the stream, it must be proven from the generator.
> Joe
I made a guess that this guy came up with these numbers on a rush. And
I'm 99% sure of that. It's not a 100% guess but under the circumstance,
I know I'm right! :)
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: chap authentication scheme?
Date: 11 Aug 2000 01:15:11 GMT
In <8ms9ke$dlu$[EMAIL PROTECTED]> [EMAIL PROTECTED]
(David A. Wagner) writes:
]Mark Wooding <[EMAIL PROTECTED]> wrote:
]> David A. Wagner <[EMAIL PROTECTED]> wrote:
]> > Bill Unruh <[EMAIL PROTECTED]> wrote:
]> > > The authenticator has a modulus N (prime?) and a generator g. The stuff
]> > > stored in the database is
]> > > username, salt s, g, N, g^ps modN
]> > > The challenge to theuser is
]> > > s,N, g^x modN where x is a random number
]> > > Response is
]> > > (g^x modN)^ps modN
]> > > which the authenticator can compare with (g^sp modN)^x modN
]> >
]> > There is a problem with active attacks. Any malicious party can
]> > pretend to be the server, pick a random x, challenge the user, and
]> > from the user's response learn the user's password. The user has no
]> > way to know that this has happened, since the server is not
]> > authenticated in any way.
]>
]> Can you explain this attack in more detail, please? I can't see how it
]> works.
]Sure. The fake server can send any g,N he likes, including ones for
]which he can compute the discrete log. (I think you mentioned this.)
]As a trivial instance, he can pick a small N. This one is detectable, but
]there are other subtle ways to send `trapdoor-ed' and otherwise-insecure
]choices of g,N. I think this deserves some attention; it looks a little
]tricky, if you don't want the user to have to know g,N in advance.
]If g,N are fixed and known in advance and hard-coded everywhere, then
]this attack doesn't work. But the original post showed them sent on
]the wire to the user, which is why I assumed there is an attack.
]By the way, there's a second attack here, if you don't expand the password
]using, e.g., OAEP. It _does_ apply even if g,N make the discrete log
]hard. Suppose you use a truly-random 100-bit quantity as your password p.
]You might expect that this would be secure. But it's not. There are
]square-root attacks (e.g., Shank's attack) which can take advantage of the
]fact that we know h, h^p mod N where p lies in relatively small interval.
]This is easy to fix: use OAEP or an equivalent.
OK, instead of storing g^ps in the database, you store MD5(g)^p, where
you take g to be unique to each user in the
database. This means that the server cannot choose a g which makes
factoring easy, since he cannot go backwards from MD5(6) to find the
right g. Then everwhere in the protocol, MD5(g) is used instead of g,
except that it is g that is sent in the challenge.
So the modified procedure is
Call M(g)=MD5(g) modN (or use any other cryptographic hash).
Store g, M(g)^p,N
g is unique to each user. (It could for example be the username)
Challenge g, x,N (x a random number).
Response M(g)^(M(x)p) modN
Comparison to (M(g)^p)^M(x)
This gets rid of the salt as well, since each user has a different g.
This is of course still liable to a dictionary attack, but I do not
think you can get around that with only a two way exchange.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: The quick brown fox...
Date: Fri, 11 Aug 2000 01:18:11 GMT
On Thu, 10 Aug 2000 08:18:15 -0600, [EMAIL PROTECTED] (wtshaw) wrote,
in part:
>Without disputing the chance of the sentence, "The quick brown fox jumps
>over the lazy dog," being observationally illustrated, we know that it
>contains all twenty-six letters we commonly use.
>Requiring the whole alphabet, does anyone know of other alternatives,
>perhaps shorter ones and with no increase in nonsense content?
One somewhat shorter one, but still longer than 26 letters, is:
Pack my box with five dozen liquor jugs.
I remember seeing it in a typefounder's specimen book; I suppose,
though, that the subject matter was considered unsuitable for the
young ladies in typewriting classes.
John Savard (teneerf <-)
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Best AES candidates ?? Slow Skipjack might have advantage
Date: Fri, 11 Aug 2000 01:20:39 GMT
Actually, the advantages of a slow algorithm - or, more specifically,
a fast algorithm with slow key setup - for hindering brute-force
search _were_ thought of before.
Have we all forgotten Blowfish so soon?
John Savard (teneerf <-)
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Interesting new Rijndael paper by Robshaw & Murphy:
Date: 11 Aug 2000 01:32:02 GMT
In article <[EMAIL PROTECTED]>,
Sam Simpson <[EMAIL PROTECTED]> wrote:
>"Rijndael splits very cleanly into a layer of S-box transformations,
>a linear diffusion layer designed to provide mixing across the block,
>and a subkey layer.
>
>In this note we consider the linear diffusion layer of Rijndael. We
>derive the interesting property that any input text (or any input
>difference) to the linear diffusion component of Rijndael is always
>mapped to itself after at most 16 applications of the linear
>diffusion transformation. "
>
>http://isg.rhbnc.ac.uk/mrobshaw/
>
>--
>Sam Simpson
>Comms Analyst
>http://www.scramdisk.clara.net/ for ScramDisk hard-drive encryption &
>Delphi Crypto Components. PGP Keys available at the same site.
>
>
>
I wrote some Magma code which I used to independently verify some of
their observations (the computation of the linear diffusion matrix,
its characteristic polynomial, and its minimal polynomial). The code
is below.
For information on Magma, please see:
http://www.maths.usyd.edu.au:8000/u/magma/
Scott
==============================================================================
/*
Remarks on representation:
Given input byte matrix of the form:
a_11 a_12 a_13 a_14
a_21 a_22 a_23 a_24
a_31 a_32 a_33 a_34
a_41 a_42 a_43 a_44
we represent it as a vector of bytes column-wise. Thus, the vector
representation for this is:
[a_11 a_21 a_31 a_41 a_12 a_22 a_32 a_42 a_13 a_23 a_33 a_43 a_14 a_24 a_34 a_44]
Because of this, the ShiftRow changes things quite different than one would
expect (see below). If we were to represent these vectors row-wise, then
ShiftRow would appear more normal but MixCol would become completely screwy.
Hence somewhere you have to make some sacrifice.
To reproduce the Murphy/Robshaw results, we actually have to represent
everything in bits rather than bytes. So we expand these matrices and
vectors in a natural way. By the Murphy/Robshaw convention, most significant
bits come first.
*/
/* Create the ByteSub transformation (known as 'L' in Murphy/Robshaw
paper)
*/
seq := [
1,1,1,1,1,0,0,0,
0,1,1,1,1,1,0,0,
0,0,1,1,1,1,1,0,
0,0,0,1,1,1,1,1,
1,0,0,0,1,1,1,1,
1,1,0,0,0,1,1,1,
1,1,1,0,0,0,1,1,
1,1,1,1,0,0,0,1
];
L := Matrix(GF(2),8,8,seq);
/* Create the 128x128 matrix corresponding to multiplying all bytes by L */
linear_diffusion_layer := IdentityMatrix(GF(2), 128);
for j in [1..128 by 8] do
InsertBlock(~linear_diffusion_layer, L, j, j);
end for;
/* 8 by 8 identity matrix */
i8 := IdentityMatrix(GF(2), 8);
/* Create the ShiftRow transformation. First we the matrix M which
acts as ShiftRow bytewise: It takes the bytes
[a_11 a_21 a_31 a_41 a_12 a_22 a_32 a_42 a_13 a_23 a_33 a_43 a_14 a_24 a_34 a_44]
to
[a_11 a_22 a_33 a_44 a_12 a_23 a_34 a_41 a_13 a_24 a_31 a_42 a_14 a_21 a_32 a_43]
*/
M := IdentityMatrix(GF(2), 16);
SwapRows( ~M, 2, 6 );
SwapRows( ~M, 3, 11);
SwapRows( ~M, 4, 16);
SwapRows( ~M, 6, 10 );
SwapRows( ~M, 7, 15 );
SwapRows( ~M, 8, 16 );
SwapRows( ~M, 14, 10 );
SwapRows( ~M, 12, 16 );
/* Now create the corresponding bit-level matrix, which we will call big_M */
big_M := Matrix(GF(2),128,128,[0: i in [1..128^2]]);
for i in [1..16] do
for j in [1..16] do
if M[i][j] eq 1 then
InsertBlock(~big_M, i8, (i-1)*8+1, (j-1)*8+1);
end if;
end for;
end for;
linear_diffusion_layer := big_M*linear_diffusion_layer;
/* last step: the MixCol transformation. This is called the matrix D
in the Murphy/Robshaw paper. Let GF(2^8) be represented by
GF(2)[t]/m(t) where m(t) is t^8 + t^4 + t^3 + t + 1 . We have
to be able to multiply elements in GF(2^8) by only the following
fixed polynomials: 1, t, t + 1 . First create the matrices corresponding
to this mutliplication. Note that i8 (already created) corresponds
to multiplying by 1.
*/
multbyt := Matrix( GF(2), 8, 8, [0: i in [1..64]]);
for i in [1..7] do
multbyt[i][i+1] := 1;
end for;
multbyt[8][1] := 1;
multbyt[7][1] := 1;
multbyt[5][1] := 1;
multbyt[4][1] := 1;
multbytplus1 := multbyt + i8;
/* Create a 32x32 matrix called mix_col which corresponds to multiplying
one column of the state by c(x) = `03'x^3 + `01'x^2 + `01'x + `02'
mod x^4 + 1 . Recall from the Rijndael paper that this is equivalent
to multiplying the input column Transpose(a_0 a_1 a_2 a_3) by the
matrix
02 03 01 01
01 02 03 01
01 01 02 03
03 01 01 02
where operations are done in GF(2^8) .
*/
mix_col := IdentityMatrix(GF(2), 32);
InsertBlock(~mix_col, multbyt, 1, 1);
InsertBlock(~mix_col, multbytplus1, 1, 9);
InsertBlock(~mix_col, i8, 1, 17);
InsertBlock(~mix_col, i8, 1, 25);
InsertBlock(~mix_col, i8, 9, 1);
InsertBlock(~mix_col, multbyt, 9, 9);
InsertBlock(~mix_col, multbytplus1, 9, 17);
InsertBlock(~mix_col, i8, 9, 25);
InsertBlock(~mix_col, i8, 17, 1);
InsertBlock(~mix_col, i8, 17, 9);
InsertBlock(~mix_col, multbyt, 17, 17);
InsertBlock(~mix_col, multbytplus1, 17, 25);
InsertBlock(~mix_col, multbytplus1, 25, 1);
InsertBlock(~mix_col, i8, 25, 9);
InsertBlock(~mix_col, i8, 25, 17);
InsertBlock(~mix_col, multbyt, 25, 25);
/* create the full 128x128 matrix corresponding to the MixCol
transformation.
*/
big_mix_col := Matrix(GF(2),128,128,[0: i in [1..128^2]]);
InsertBlock(~big_mix_col, mix_col, 1, 1);
InsertBlock(~big_mix_col, mix_col, 33, 33);
InsertBlock(~big_mix_col, mix_col, 65, 65);
InsertBlock(~big_mix_col, mix_col, 97, 97);
linear_diffusion_layer := big_mix_col*linear_diffusion_layer;
time m<x> := MinimalPolynomial(linear_diffusion_layer);
m;
time c<x> := CharacteristicPolynomial(linear_diffusion_layer);
c;
------------------------------
Date: Fri, 11 Aug 2000 13:59:33 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: OTP using BBS generator?
=====BEGIN PGP SIGNED MESSAGE=====
Terry Ritter wrote:
> lcs Mixmaster Remailer <[EMAIL PROTECTED]> wrote:
> >Terry Ritter writes:
> >> The LSB of the x^2 mod N result *is* the output of BB&S. If a cycle
> >> of LSB's could be shorter than the cycle itself, BB&S would be
> >> seriously damaged. To the extent that there is a proof of BB&S, that
> >> proof must cover this situation, because this *is* BB&S.
> >
> >This is correct. It is frustrating that you have come so close here to
> >understanding the position of those who have been arguing against you
> >for so many years.
>
> On the contrary, I think I understand that position well, while you
> clearly have serious problems understanding mine:
>
> The very fact that you are willing to trust a "proof" which overlooks
> a known and demonstrated (if infrequent) weakness, leads me to believe
> that we do not have the same understanding of what "proven secure"
> should mean in cryptography.
>
> I DO NOT ACCEPT that a cryptosystem which has a known potential
> weakness can legitimately be called "proven secure."
OK, in that case you must not accept that BBS is proven secure at all,
under any assumptions, and with or without the cycle checks.
It might clarify the argument if you could confirm whether or not that is
actually your view.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOZPQTzkCAxeYt5gVAQFsZggAy5Se5eEzK/B1YIKFXcVe5RjXNPPKjW79
ey/CGBF4uI2iT9UOplpLZTZb6Sf8Kq/zNp5zZil1ZAsc2U9/OOuMQ5SOFd/287Fr
4bB7sK4jNtlH39nglqKYtqXEK98WaG40pbLJRq3FYs955fkq7QP8rDEGTyyidHZp
yAf1hCDXllUB8iLbDJIqJEvl3vNfWM2XfJepIYMb6z507YYkr4PkPTucVMVjAhQU
ILmWLZPW5FEf28/hGhBJwVBEGXrzuZu72RBVIC6u64vDT4Use/Jb16Q5Ex1I9xkr
FPFme9+mYJFqp0ooj7NrqMQPDY3DqKVxWnAQp29LbuGWzNoRjFiUkQ==
=M7K1
=====END PGP SIGNATURE=====
------------------------------
Date: Fri, 11 Aug 2000 13:59:44 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: OTP using BBS generator?
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
> Terry Ritter wrote:
>
> > With a statistical approach, we might prove that something "almost
> > always works." That's a fine goal; I have no problem with that sort
> > of proof. My problem is with implying that "proven almost always
> > secure" means "proven secure." It does not. A far better description
> > would be "a statistical proof of security."
>
> In another follow-up I have argued for a replacement of the
> term 'provable security' without having considered statistics.
> Here is a modified version:
>
> 'existence of a rigorous security proof of statistical
> nature contigent on fulfillment of certain assumptions'
Proofs in this area of cryptology are generally probabilistic, but they are
*not* statistical (there are no "statistical tests" involved). Probability
theory is a lot less fuzzy and has a sounder mathematical basis than does
most interpretation of statistical results (for example reporting bias, of
which an example is given below, is a very serious problem in that context).
In any case, a phrase of the length suggested above is far too much of a
mouthful to expect anyone to use it in practice. Personally, I would prefer
something like "security supported by proof".
> > And we have yet another problem: How can we believe that the short
> > cycle insecurity is the *only* one which this proof allows to exist?
> > We *can* prevent the short-cycle insecurity, because we know about it.
> > But we *can't* prevent other security problems about which we know
> > nothing.
>
> In another follow-up I have used an example to demostrate
> that the strange behaviour that David Molnar found for
> non-BBS modulus can also happen in BBS. With n=209, a
> cycle of length 4 (which I found on my second trial)
> gives the LSB of 0000!
I wouldn't read anything into this - a cycle of length 4 will be 0000 with
probability 1/16, which can hardly be considered extremely unlikely. Also,
you would presumably have considered 1111 just as surprising, and you only
found this on your second trial. Finally, there is a reporting bias in the
sense that if the result had not been "surprising", you probably wouldn't
have posted the example, since it wouldn't support your argument. The nature
of Usenet tends to amplify this kind of reporting bias - we don't know
how many people tested BBS (or more generally looked for unusual output
characteristics for any cryptosystem), and found nothing at all to suggest
non-randomness.
[...]
> Now this is certainly a toy
> example. But it is on the other hand definitely a
> warning indicating that the statistical qualties (note
> that cycle length is not 'everything' of statistics!)
> should be carefully investigated, as I also suggested
> in the other follow-up (at that time rather intuitively).
> For what the toy example shows might not be, unless
> demonstrated to the contrary, a very rare chance
> happending but could well be the tip of an iceberg.
> Further, as David Hopgood
Hopwood
> pointed out and probably
> ignored by most experts till present, the BBS paper
> left open the issue of the relationship between the
> cycle length of the numbers from the congruence
> relation and the cycle length of the LSBs.
I'm sure that anyone who read the paper in full was aware of this.
However, it doesn't really matter to the security of BBS; the
proof that the LSBs (not the x_i values) are indistinguishable from
random except with negligable probability and under the assumption that
factoring is intractable, does not depend on any unproven conjectures
about cycle length.
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOZPcETkCAxeYt5gVAQENBAgAhvu40tLv4RReBc/TBj3TjJzsYoOMemyM
WgXarnJ9ivojlP+CvBAGNiFaAFs1RoA527DNh01yqpUN3XI4OFaQCAQ+Dxja9NUP
JSq2HsO5ny4qK2hUYqZvHRRu5n8vH3jyXQCd3jQrAKpQS5hEiNL+DrwCYuV23MQj
9BnWIx+3WjtCmleyhOVKRWBwazlFqZdi9Wt6iO/3XGbCV4tcubWVqdrXIwfNDCrt
25CQwwGBgy9XhQpaRR2/SbZCUIrZwzKRyA+52YdfvB5MP6e9W4j8Y8Kj01DlPvo9
l/jFh0WIYViLq0i9WasjwLUGSnYNXbAJUUVpfOIPCbRqxUrPiunFwA==
=c8pG
=====END PGP SIGNATURE=====
------------------------------
** 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
******************************
