Cryptography-Digest Digest #901, Volume #13 Wed, 14 Mar 01 23:13:01 EST
Contents:
Re: Analysis of PCFB mode ("Henrick Hellstr�m")
Re: Problem with BBS implementation ("Joseph Ashwood")
Re: BBS ("Joseph Ashwood")
Re: One-time Pad really unbreakable? ("Joseph Ashwood")
Re: Again on key expansion. ("Joseph Ashwood")
Re: One-time Pad really unbreakable? ("Joseph Ashwood")
Re: One-time Pad really unbreakable? ("Joseph Ashwood")
Re: hardwire prime & generator in Diffie-Hellman? ("Joseph Ashwood")
Re: Quantum Computing & Key Sizes ("Douglas A. Gwyn")
Re: hardwire prime & generator in Diffie-Hellman? ("Joseph Ashwood")
Re: Super-strong crypto......................(As if). ("Joseph Ashwood")
Re: primes for BBS (Benjamin Goldberg)
----------------------------------------------------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Analysis of PCFB mode
Date: Thu, 15 Mar 2001 04:01:52 +0100
David Wagner is absolutely right. I posted that proposal in a haste a month
back and planned to send a revised version soon thereafter. Unfortunately
that didn't happen. So now I am trying to put together all the pieces David
Wagner, Scott Fluhrer and a few others kindly helped me with.
I have inserted a few comments below.
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"David Wagner" <[EMAIL PROTECTED]> skrev i meddelandet
news:98ouos$3dh$[EMAIL PROTECTED]...
> I just took a look at PCFB mode:
> http://csrc.nist.gov/encryption/modes/proposedmodes/pcfb/pcfb-spec.pdf
> The proposal seems to suggest that it can be used to provide both
> confidentiality and message integrity (when there is sufficient
> redundancy in the plaintext). However, it seems to have a few
> undesirable properties.
>
> The proposal leaves two critical details unspecified:
> - The redundancy scheme (for integrity) is not described.
> - The parameter m, which describes the number of bits encrypted per
> block cipher operation, is unspecified.
> Both of these areas have pitfalls. Unfortunately, it is left up
> to the implement to puzzle out these design choices for herself
> (no guidance -- or even warning of the risks -- is provided in
> the specification of the mode as proposed to NIST).
Absolutely. I'll try to deal with this.
> First, it seems difficult to choose m so that PCFB mode becomes
> competitive. If m is too small, PCFB mode is inefficient. With
> m=64, PCFB mode is already twice as slow as other integrity modes
> (IACBC, OCB, XCBC, etc.), which suggests that there will be strong
> pressure to choose m >= 64.
In the revision I specify m by the formula n=m2**k, for some positive
integer k. You are right that PCFB mode is slower than the modes you
mention. On the other hand PCFB mode is the only one which allows a space /
time trade off, in the sense that you could choose m=8 as a way to get rid
of the padding of the last block (and use some elaborate redundancy checks
to get rid of the MAC block at the end).
> However, when m is large, the
> error-propagation mechanism has some perhaps-undesirable properties.
> In particular, PCFB has only 128-m bits of internal state (when
> used in decryption mode), so by the birthday paradox we can expect
> to see collisions in the internal state after about 2^{64 - m/2}
> blocks of ciphertext, which might raise questions about security.
> So we could be stuck between a rock and a hard place in choosing m.
It would certainly be good to take a very close look at this property, but I
am not sure that it is a problem at all. The internal state will not be
caught in a cycle just because a value of the internal state occurs a second
time. If the plain text / cipher text does not have exactly the same cycle
as the state, then the cipher feedback will break the cycle.
Maybe I am just tired (it's 3:45 a.m. local time), but as a matter of fact I
don't get your figures to compute. The state is always 128 bits. However,
only 128-m bits of the state is secret, but there is considerable diffusion
involved in the step from the 128-m secret input bits blended with the
(known) cipher text, to the secret 128-m output bits.
Hence, I imagine that you would have to decrypt a m-bit periodic cipher text
to expect a collision after 2**{64 - m/2) blocks. (I also believe that this
is provable: We are not dealing with Schr�dinger cat and such quantum physic
phenomena. You wouldn't expect collisions every block if you knew all bits
of the state.) So I figure that David Wagner's intention is to outline
either some kind of chosen cipher text attack, or the foundation of a
statistical attack against a stateless PCFB derivate which includes a reset
of the state every message without changing the key. Correct me if I'm
wrong. If I am not, all that seems to be asked for is more precise usage
specifications.
> Second, PCFB mode is insecure when used with some redundancy schemes.
> Consider what may be the most natural scheme of all: we append 128
> zero bits to the message before encryption, and on decryption we check
> that these bits have not been disturbed. Yet such a scheme is insecure
> against chosen-plaintext attack: We can ask for the encryption of
> the chosen message X || 0 || Y, and then truncate the ciphertext just
> before the "Y" part. The result will be a valid encryption of X;
> since the sender may never have authorized the transmission of X, this
> is an integrity failure.
True. There are better alternatives. The scheme I described in the present
specification is to encrypt 0 || k0 || X1 || 0 || k1 ..., where k0, k1, ...
are random numbers selected by the sender and X1 is the first k0 bits of
plain text etc. Consequently you have to ask for the encryption of 0 || k0
|| X1 || 0 ..., but the output you would get would have an additional zero
and number k0' in front, and the cipher text won't decrypt properly if you
truncate the front of the message.
... and just out of curiousity or perhaps lack of imagination ... What makes
the method you describe in your example into a possible attack? True, X
alone might have a completely different meaning than the concatenation X ||
Y. But the attack presupposes that the attacker is able to control not only
the sender's choice of at least one plain text block but also the choice of
the position at which the recipient should expect the authentication code
(i.e. the string of zeroes). If you have this kind of control you could
mount exactly the same attack against e.g. XCBC mode, in this case simply by
correspondingly asking for the encryption of X || g(X) || Y.
> It seems plausible that PCFB mode may be
> secure under some other choice of redundancy scheme, but if history
> is any guide, it would be prudent to step with considerable caution.
> (There have been many similar proposals intended to provide integrity,
> but almost all have since been broken. The only exceptions I am aware
> of are a few recent modes that have been proven secure.)
"Proven secure against well defined attacks given some reasonable
assumptions about how the mode is used, about the underlying cipher and
about the knowledge and ability of the attacker", yes. At the present moment
I have no reason to doubt that PCFB mode too is provably secure in this
sense, provided that it is used with a suitable authentication scheme.
(Disclaimer: Note that I wrote "provably" and not "proven", since as far as
I know no such formal proof has been published yet. Sometimes I am wrong, so
I am glad there is a David Wagner out there to correct me on those
occasions. ;-))
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Problem with BBS implementation
Date: Wed, 7 Mar 2001 12:50:50 -0800
"Dobs" <[EMAIL PROTECTED]> wrote in message news:985qa9$jmt$[EMAIL PROTECTED]...
> ok thanks for answer, maybe U can also tell me where can I find a source
> code of such a large prime numbers generator which can I use in this
program
www.openssl.org has a very nice one, that it easy to understand.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: BBS
Date: Wed, 7 Mar 2001 12:59:16 -0800
What BBS needs is for the primes to be replaced before the modulus can be
factored. This is generally harder to guess than it is to simply replace
them for each new use.
Lately I've found myself very often recommending the BIGNUM package in
openssl (www.openssl.org), it's fast it's good, and it can generate those
big primes for you with a single call, and can do so rather quickly.
Joe
"Dobs" <[EMAIL PROTECTED]> wrote in message news:9862va$mqp$[EMAIL PROTECTED]...
> I have a question. How should good Blum Blum Shub Generator looks like? I
> know that it needs 2 large prime numbers p and q. Should this generator
have
> its own large prime number generator to generate new p and q each time we
> found our seed. Or it does not metter and I can for instance declare that
p
> is such and q is such.
> If it needs generator can somebody tell me one wchich would be proper for
> BBS, I mean will generate large prime numbers:
> Best Regards:)
> Michal
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Date: Wed, 7 Mar 2001 12:39:08 -0800
[comments afterward]
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In that case, Las Vegas ought to find another industry with which to
> support itself.
>
> In other words: here is a counterexample - a sequence of physically
> generated random numbers that cannot effectively be predicted. The
> series of numbers generated by throwing dice and the like is indeed
> sufficiently clearly unpredictable that the mathematical proof of the
> OTP is still highly relevant - even if the unbreakability of a "real"
> OTP is no longer at the absolute level of truth of a mathematical law,
> it is still quite obviously at a high enough level of confidence to
> warrant no concern over attacks based on using the previous key to
> determine the position of all the molecules in the room and so on.
That is not necessarily the case. What the casinos depend on is there being
such a small number of people (either through luck, psychic abilities,
cryptanalysis, etc) who can predict the happenings that they can be ignored,
just as we ignore the possibility of someone guessing a 128-bit number on
the first try. If this were not the case they would have to use only perfect
dice, and that, like perfect random numbers, is something that we don't know
how to do. They also stack the odds in fovor of randomness, if you look at
the rules (to any game that is something other than a gimmick), they are
setup so that if the dice have a bias that bias cancels itself out, or works
in favor of the house.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Again on key expansion.
Date: Thu, 8 Mar 2001 11:19:57 -0800
"Cristiano" <[EMAIL PROTECTED]> wrote in message
news:988hj3$dq1$[EMAIL PROTECTED]...
> However, I think that a method based on time is not a good method because
if
There is only one other measure, cost. And with computers we already know
you can trade off time and cost.
> I stretch for 1 s my password with my old commodore64, on my amiga1200 the
> same number of iterations will takes .01 s, on my pc .0001 s.
However in all cases it will have added the same amount of "entropy".
> Doesn't a better method exist?
A better method can't exist. You can only measure this by the
time/cost/work, where work = time*cost. To double the work, you must double
the time, or the cost. You simply cannot get around that.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Date: Thu, 8 Mar 2001 11:42:38 -0800
There are many different categories of proven.
Radioactive decay has been proven to be unpredictable without knowledge of
the internals of that particular atom (under certain assumed models of
quantum physics which are a hot point of debate among physics people, and
probably will be for as long as either of us lives). That is not enough for
OTP security, OTP security requires that it be proven that given infinite
knowledge about the state prior to, the state after, and infinite knowloedge
of the universe (with the exception of what came out of the RNG) it is
impossible to predict with probability greater than 1/b (where for our
purposes b is 2). That is a very hard proof. What we can prove is that
certain things are not an influence, and with radioactive decay, it has been
established that if placed in an isolated universe (no other particles) it
does not change the outcome, however the atomic bomb proves that being
surrounded by a particular concentration of particular particles can cause
averse rates of not so random numbers (e.g. Hiroshima, Nagasaki). This
indicates that the radio-active decay model may in fact be subject to the
"kick the box" attack to skew the random numbers.
Joe
"Mxsmanic" <[EMAIL PROTECTED]> wrote in message
news:ISQp6.79288$[EMAIL PROTECTED]...
> "Paul Crowley" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
>
> > We have many sources of random numbers that
> > *seem* to be effective in *practical* terms, but
> > none of them are *proven* effective the way
> > the one-time-pad is *proven* effective.
>
> My understanding is that the randomness of radioactive decay is
> _proven_, not merely postulated, because it is an inevitable consequence
> of quantum mechanics as that theory is now understood. Calling it
> non-random would be like saying that repulsive gravity exists.
>
>
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: One-time Pad really unbreakable?
Date: Thu, 8 Mar 2001 11:49:50 -0800
"Frank Gerlach" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> If you call the widely used SIGSALY (check www.nsa.gov for it)
> "mathematical never-never land"
> then you are correct.
All that shows is that there is a point where we have to call it "good
enough" however "good enough" is not a useful term when discussing the
perfect security of a OTP.
> I assume that OTPs are still used every day, especially by intelligence
> services.
> OTPs have the nice property that you can easily do it by hand/paper, and
> nobody will be able to
> break it, if you use it *disciplined* and have the keys correctly
> generated.
There's the problem right there; "keys correctly generated" I do not
question that some randomness exists (I'd dread living in a universe where
my typing this was decided by where a particular particle was during the big
bang). Correctly generating keys takes a provable random source, so far the
proof of any source has evaded the public.
> The russian KGB and the german BND regularly used it during the cold war
> to communicate
> with their agents operating in enemy territory. Why should they stopped
> using it ?
I have no doubt that they did. However many of those "One Time Pad"s were
broken because they were in fact coming from a complicated but deterministic
machine. The Russians also had problems with their pullers not putting the
numbers back which lead very quickly to biases.
> The TV lottery shows us week that good OTP keys *are* possible.
Incorrect. What the TV lottery shows is that it is possible to have a
situation that looks random enough to modern man that no one can
successfully attack it at this time, or at least that a small enough
percentage of people can attack it as to declare them moot in the overall
scheme.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: hardwire prime & generator in Diffie-Hellman?
Date: Thu, 8 Mar 2001 11:57:49 -0800
[send both privately and to newsgroup (not that my messages seem to be
making it there right now)]
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message news:%QCp6.42337
> Actually I made up sqrt((p-1)/2) I wanted to see if anyone would notice.
> Typically you can't make enough keys to find a collision if your prime is
> big enough.
You may have made up sqrt(p-1/2) but it's a very valid line. Since G is a
generator the distribution probabilities will match the RNG, with a good RNG
how soon would we expect a collision? about sqrt(n). Moving the sqrt to be
on p has no effect provided that x is chosen to be in that range.
Subtracting one has no effect here except to make the divide by 2 an
integer. The divide by two effectively divides the result by sqrt(2) which
is, in this scheme of things at best a safety margin. So while it may be
"made up" it's actually a very close guess. However for saftey I would
recommend sqrt(sqrt(p)) instead, the odds of a collision are microscopic,
especially when we're dealing with numbers >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
2^128.
Joe
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computing & Key Sizes
Date: Thu, 15 Mar 2001 03:17:27 GMT
Simon Johnson wrote:
> Whats special about a quantum computer ...?
The idea is that it can process a superposition of possible
states simultaneously, a way of getting massive parallelism.
That raises further questions, like how can one read out the
answer. Best to read a tutorial somewhere.
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: hardwire prime & generator in Diffie-Hellman?
Date: Wed, 7 Mar 2001 17:45:34 -0800
"Julian Morrison" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> 1) What is the security implications of hardwiring in the prime/genrator
> startup pair for DH key exchange? Does it compromise the protocol or is
> it safe?
Provided you take some extra precautions, like making it a strong prime,
building in a margin of error to your choice, etc. There is no problem. As
Tom said you can use up up to around sqrt(p-1/2) messages, this isn't going
to be a problem, after including the margin of error you'll probably have a
2048-bit prime. The square root of that is going to be over 2^1000
(~10^300), theoretically if you could grab that many messages you could
break the system with some effort, but considering that the standard quote
on counters is that you would have to harvest 100% of the energy from the
sun for a full year to clock to 2^271, you would need to gather all the
energy from the entire known universe for the entire lifespan of the
universe, and I still don't think you'd get to 2^1000. I think it'll be
safe.
>
> 2) If it's safe to do this, does it become more safe the larger the prime
> is?
Yes the large the primes the safer.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Super-strong crypto......................(As if).
Date: Wed, 7 Mar 2001 12:49:20 -0800
Quick contradiction:
Large hard drive is 150 GB
150 GB = ~ 2^37
37-bits worth of security is trivial (reference RSA DES Challenge III:
56-bits = 22 hours).
I'm sorry but seperation/recombination is not the solution. Even techniques
to square the space would only give you 74 bits, and the minimum considered
secure is 80-bits. You are completely and utterly wrong.
Joe
"Keill_Randor" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> The only way to have a secure encryption system, (and uncrackable), is to
make sure that the only way to crack an encrypted peice of data - (or any
other peice of information - (I just concentrate on computing)), is to run
through every peice of data known to a computer - (Even the NSA won't be
able to deal with that).
>
> I.e. the only secure system, is one that allows you to encrypt any peice
of data (or stream), using any other peice / peices or stream / streams of
data.
>
> (Like what mine does, but I don't think it's a good idea to post it,
somehow..:). (I'm trying to deal with GCHQ, but they don't seem to want to
know...(Idiots))). The word random shouldn't really be needed...
>
> Keill Randor
> [EMAIL PROTECTED]
>
>
> _______________________________________________
> Submitted via WebNewsReader of http://www.interbulletin.com
>
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: primes for BBS
Date: Thu, 15 Mar 2001 03:26:12 GMT
Dobs wrote:
>
> Hello,
> I am trying to implement Blum Blum Shub generator. I need 2 large
> prime numbers p and q. Where should I take this numbers from,( I gess
> each time they generate one bit, they have to be changed) Is there
> any algorithm to obtain such a large primes, which would be right for
> BBS generator.
> Thanx, best regards
> Michal
For BBS to be secure, the primes must be many many many bits, (512 bits
each is a good size). To handle number of this size, you need a large
number package. Most large number packages include a function for prime
number generation.
Also, you do not generate a new p, q, for each bit BBS produces.
For each iteration of BBS, you calculate x := x*x mod pq. The lowest
log2(log2(pq)) bits of x each round can safely be used. If pq is a 1024
bit number, log2(pq)=1024. So the lowest log2(1024) bits of x can be
used from each iteration. Or up to 10 bits of x from each iteration.
Note that p, q, don't just have to be primes, they have to be *special*
primes (specifically "Blum integers" which are prime, aka "Blum
primes"), and when picking a starting value for x, you have to make sure
that it does not produce a short cycle.
All in all, a good BBS implementation is rather complicated. I would
advise that unless you really know what you're doing, you instead
implement something nice and simple, like ARC4.
--
The difference between theory and practice is that in theory, theory and
practice are identical, but in practice, they are not.
------------------------------
** 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
******************************
