Cryptography-Digest Digest #688, Volume #10 Mon, 6 Dec 99 01:13:00 EST
Contents:
Re: The leading university of cryptography (Yukta Mookhey)
Re: Elliptic Curve Public-Key Cryptography (Scott Contini)
Re: NSA should do a cryptoanalysis of AES (Sundial Services)
"The message is still the same." (Was Re: NSA should do ...) (Sundial Services)
Re: VIC cipher's PRNG ("r.e.s.")
Re: iaPCBC: confidentiality and integrity in one shot (long) (David Hopwood)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Yukta Mookhey)
Subject: Re: The leading university of cryptography
Date: 06 Dec 1999 00:44:14 GMT
�� �ޭz�[EMAIL PROTECTED] (David A Molnar)�n���ʨ��G
[del]
> You might try looking at a list of cryptographers (David Wagner has one
> on his site, so does Kevin McCurley) and picking out those whose work you
> admire. Then see where they are located. That will probably tell you more
> than I can about which universities are strongest in the kind of crypto
> you like.
[del]
Here are they:
David's: http://www.cs.berkeley.edu/~daw/people/crypto.html
Kevin's: http://www.swcp.com/~mccurley/cryptographers/cryptographers.html
Enjoy them. :)
--
[1;32m�� Origin: [37m<Terry.Dragon2.Net> [m
[1;31m�� From: [36mterry.dorm8.nctu.edu.tw[m
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Elliptic Curve Public-Key Cryptography
Date: 6 Dec 1999 02:38:10 GMT
In article <827g7l$6a5$[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
>Michael Scott <[EMAIL PROTECTED]> wrote:
>>
>>DJohn37050 <[EMAIL PROTECTED]> wrote in message
>>> I said I had seen a performance sheet at least a year ago where ECC
>>>163-bit was more like the performance of 17 bit exponent RSA 1024 bit
>>>key. (ballpark). I know this info was presented at a PKS conference a
>>>few years back.
>>
>>This rather surprising claim is made in
>>
>>http://www.certicom.com/ecc/wecc4.htm
>
>Thanks. I looked at that page and it says BSAFE 3.0 took 12.7 msec to
>do a 1024 bit RSA verification, and that Certicom's two ECC methods in
>Security Builder 1.2 took 9.9 and 10.7 msec respectively, both on a
>167 MHz Ultrasparc.
>
>I don't have a 167 mhz Ultrasparc available but have been doing some
>timings on a 300 mhz unit (Sparc Ultra 5) so have some scaled figures.
>It makes me think the BSAFE 3.0 numbers are way slower than what can
>be done on that Ultrasparc. I've been told that BSAFE 3.0 is a
>portable C implemetation without any assembler speedups. I believe
>RSA has something better by now.
Yes, I am quite sure that RSA's BSAFE 3.0 had only a C implementation
of RSA on the Ultrasparc. An assembly implementation would give
a very strong speedup (approx. a factor of 4) since a 64-bit product
can be obtained from 32-bit multiplies (I do not know how much
the floating point unit can be used to speed up arithmetic, but RSA
is against using floating point arithmetic in their code because of
portability reasons). I'm quite sure RSA has a more efficient
implementation for the Ultrasparc in BSAFE 4.0. It would be nice
if somebody out there could post some timings for BSAFE 4.0.
>
>Meanwhile, the web page says the ECC implementation uses "performance
>enhancing techniques" which I'm guessing means using precomputed
>powers of the generator (as is commonly done for El-Gamal) burning a
>lot more storage space.
That is likely to be true, and it is fair to do such precomputations,
but the poster (Certicom) of the benchmarks should give some details on the
memory usage for their benchmarks to be meaningful. Certicom's
timing comparisons are bogus because they omit the details of HOW
such timings were obtained - such precomputations are not going to
be possible on many small devices. Anyway, to my knowledge, these
precomputations can speed up an ECDSA verify by at most a factor of
2 (since you can only precompute for the base point), so this (alone)
should not have a huge impact on the timing comparisons.
>
>With the OpenSSL library as distributed (www.openssl.org), on the Ultra 5,
>I get 411 verifications/sec with the built-in benchmark
>("openssl speed rsa1024"). Scaling by a factor of 2 for the 166 mhz
>processor that would be about 5 msec/verification, better than twice as
>fast as either BSAFE 3.0 or the Security Builder ECC implementation.
>
>It doesn't stop there. Although it's written in assembler, OpenSSL's
>RSA implementation on the Ultrasparc isn't very good either. The
>reason is that the Ultrasparc has a slow integer multiply instruction
>(similar to the original Pentium), and OpenSSL's implementation
>depends on it. OpenSSL on the 300 Mhz Ultrasparc is almost twice as
>slow as OpenSSL on a 300 mhz Pentium II (which has fast integer
>multiplication). The fastest way to do RSA on the Ultrasparc is to
>use floating point arithmetic, similar to how MIRACL does it on the
>Pentium. I've heard that this produces about a 3x speedup compared to
>what OpenSSL comes with. I don't have a floating point Ultrasparc
>implementation to play with right now, but am trying to get one. That
>should bring the verification speed to under 2 msec.
>
>Finally, the Security Builder benchmark appears to have been done with
>a Koblitz curve, according to some email I've received. (I don't know
>if this is the ANSI X9 curve that Don mentioned). My correspondent
>says produces a 4x speedup over a randomly chosen curve. (Me, I know
>close to squat about the math of ECC, but I'm really a lot happier
>doing things in characteristic p than characteristic 2).
Right, Jeri Solinas shows how Koblitz curves can be used to speed up
arithmetic by a factor of 4 in his Crypto '97 paper "An improved
algorithm for arithmetic on a family of elliptic curves". The
paper and the mathematics are quite nice. HOWEVER, there are security
issues with these curves. Right now it is known that the additional
structure that Koblitz curves have can be used to speed up the
Pollard rho/parallel collision search attacks - the amount of the
speedup is not enough to consider them cryptanalyzed yet. But there
are strong reasons to avoid these curves since they may turn out
to be much weaker than randomly chosen curves. I have talked to several
experts on this subject and many are skeptical on how strong these
curves are for cryptography. The main reason seems to be the small
class number of the endomorphism ring (it is a UFD for Koblitz curves),
which is also a problem for curves generated by the complex multiplication
method (although they have slightly more complex endormorphism rings than
Koblitz curves).
Again I would suggest that people do not take such timing comparisons
seriously unless all details of the comparison are given. Both
Certicom and RSA will play their marketing games, so it is up to
the scientific community to do the real comparisons.
>
>Conclusion: I believe at this point that the claim that 163-bit ECC
>signature verification speed is comparable to 1024 bit RSA, at least
>compared to a good implementation on the Ultrasparc, is thoroughly
>bogus. Bruce's estimate that it's comparable in speed to 1024 bit RSA
>with 64-bit random e sounds a lot closer to reality. I don't hold the
>confusion against Don, since as he says, speed measurements aren't his
>specialty; but some of us out here need to deal with real
>implementations, and we do worry about such things and like to have
>accurate numbers.
I agree.
Scott
------------------------------
Date: Sun, 05 Dec 1999 20:10:28 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: NSA should do a cryptoanalysis of AES
But something =else= has happened in this case! Suddenly, with the
emergence of the Internet, there was a huge explosion in the number of
cryptography-users, in the number of messages sent in cryptosystems, and
in the number of people who could be seriously harmed by a weakness in
the systems being used. (The "one person losing 50 million dollars"
scenario is replaced by "one million people losing 50 dollars," which is
worse.)
The military can take care of itself -- what was totally exposed in this
case, in the pants-down sense of the word, was the non-military public.
I think that the idea of doing an AES project to service that need was
an inspired one. It advanced and challenged the cryptographic
state-of-the-art in the non-military sector without revealing or
compromising anything in the military sector, which for its own reasons
must cling to its curtain of secrecy. We have passed beyond the time of
DES, when the government handed us a very strong algorithm and couldn't
tell us why it was strong, to a time when the AES candidates, and the
evaluation of them, came from and operated entirely within the
non-military establishment.
No doubt, the NSA *has* done a cryptanalysis of the AES candidates. No
doubt it can solve them. But that's not the point: AES was
commissioned to address the exploding new (and very, very genuine)
cryptographic requirements of the *non-military* sector. And that is a
requirement that did not -exist- five years ago.
We live in interesting times . . .
>Brian Gladman wrote:
[...]
> Becaue it a lesson about technology generally and not about cryptography in
> particular. And it stretches back into pre-history. I don't want to bore
> people with the details but my expereience has been that technolgies that
> start in the closed government world most often migrate into civil
> applications where over time more resources are deployed with the result
> that the positions of the two worlds reverse.
>
> In my career I have seen the move from defence to civil dominance in a
> number of areas - in computer systems, in integrated circuits, in software
> operating systems, in high level languages, in computer networking, in
> display technologies, and now, in my view, in computer and cryptographic
> security.
>
> What happens is that government resources tend to be constrained but can be
> spent on things that are not profitable since government does not need to
> make money. Government funded developments hence make the early running in
> new technology areas. But as civil intersts become clearer and profits
> become a driver civil resources get deployed and these are not bounded by
> the limits on government expenditure and hence eventually grow to be much
> greater in scale. Moreover, since government R&D resources are needed to
> make the next breakthrough, once civil investment develops in a technology
> area the incentive to put government money into it goes away.
>
> And I see no reason to believe that this pattern will be any different for
> cryptographic and security technologies now that the civil world has woken
> up to the need for these.
>
> Brian Gladman
--
======================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> High-speed, script-driven, table repair/support for Paradox/BDE...
> ChimneySweep{tm}: "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/cs3web.htm
------------------------------
Date: Sun, 05 Dec 1999 20:25:36 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: "The message is still the same." (Was Re: NSA should do ...)
For all the tax-money that NSA slurps up each year, and for the enormous
number of people who (like it or not, acknowledge it or not) depend upon
their cryptographic expertise to ensure that another Nazi Germany does
not appear again on this earth, I sincerely hope that they can break
most commercial systems -- and that they keep their mouths tightly shut,
as they do, about what they can and cannot do.
I still remember a poster that I saw in a hallway outside the National
Cryptography Museum. It was a WW2 poster, "Loose Lips Sink Ships," and
beneath it was printed, simply, "The message is still the same."
The grim truth of human nature is that evil people -will- use guns to
kill people by the millions given the chance to do so... and that the
best way to prevent them from doing so is by never being caught by
surprise. Yes, that means sifting through people's private
communications. Yes, that means running an enormous net. Granted 99.9%
of what you sift through will be irrelevant and discarded: but that
0.1% could be the message that alerts you to some damned fool who wants
to blow up a public building someplace in the name of some deity whom he
imagines will be immensely proud of him when he shows up at heaven's
door. We have had numerous wars to ram home those lessons -- hell, we
have WON those wars only because of those lessons. There are a lot of
us people debating this subject now who exist only because some father's
sperm was in his body after the war, because he made it through that
war, because of ... Bletchley Park or Arlington Hall, enabling his
convoy to avoid that wolf-pack that night. We know it's true, grim
though it be.
But cryptography means far more than civil libertarianism. Cryptography
is something that now has, not only military, but enormous
*non-military* requirements. That requirement is e-commerce, which was
responsible for something like $3 billion in public transactions last
year! Almost all of it protected by a none-too-strong cryptographic
tool, a recent invention called SSL. ATM machines are bloody everywhere
and -those- are protected by a government invention called DES. And so
on.
So the NSA is percolating along, on its military frequency as it always
does, in secret as it always does ... and now they're not the only game
in town. We have our secrets to protect, too.
>Bruce Schneier wrote:
>
> On Sat, 04 Dec 1999 02:21:10 GMT, albert <[EMAIL PROTECTED]> wrote:
> >If we know that the NSA broke an algorithm, it would be in their best
> >interest to share that information; because as much resources as they have,
> >they cannot beat distributed knowledge.
>
> Not necessarily. There are other differences that you have to
> consider:
>
> 1. Funding. The NSA has much more funding than the distributed
> academic world.
>
> 2. Focus. The NSA can apply a focus that the distributed academic
> world cannot. "You dozen people. Go into that room, shut the door,
> and don't come out until you've broken RC4. I don't care if it takes
> five years." That kind of focus will never happen in the distributed
> academic world, where people work on what they want to work on, and
> the coin of the realm is an academic paper.
>
> These differences, to me, mean that it is more likely for the NSA to
> solve difficult, important, problems, and more likely for the
> distributed academic world to come up with wacky, cool, interesting
> ideas.
>
> Bruce
> **********************************************************************
> Bruce Schneier, Counterpane Internet Security, Inc. Phone: 612-823-1098
> 101 E Minnehaha Parkway, Minneapolis, MN 55419 Fax: 612-823-1590
> Free crypto newsletter. See: http://www.counterpane.com
======================================================================
Sundial Services :: Scottsdale, AZ (USA) :: (480) 946-8259
mailto:[EMAIL PROTECTED] (PGP public key available.)
> High-speed, script-driven, table repair/support for Paradox/BDE...
> ChimneySweep{tm}: "Click click, it's fixed!" {tm}
> http://www.sundialservices.com/cs3web.htm
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: VIC cipher's PRNG
Date: Sun, 5 Dec 1999 18:56:05 -0800
"David Wagner" <[EMAIL PROTECTED]> wrote ...
: r.e.s. <[EMAIL PROTECTED]> wrote:
: > I was looking at the very simple PRNG used in the VIC
: > cipher, which operated with decimal digits. In pseudo-
: > code, and generalizing to base-b digits, registers
: > R(i)(i=1..b) are initialized to R(i)=key(i)(i=1..b),
: > and a stream is output by iterating the following:
: >
: > ------
: > R(b+1) = R(1) + R(2) (mod b)
: > R(i) = R(i+1) for i=1..b
: > output R(b+1)
: > ------
: >
: > What I'm wondering about is, for b>2, how to get any
: > idea of the cycle-length of the stream, e.g., how the
: > cycle-length depends on the particular (key(i),i=1..b).
:
: Yeah, there's some interesting mathematics here.
:
: Factor b as a product of prime powers, b = \prod_{j=1}^n p_j^{e_j}.
: Reducing modulo each prime power gives us n recurrence relations:
: R(i) = R(i-b) + R(i-b+1) mod p_j^{e_j}, j=1,..,n.
: Let C be the desired cycle-length mod b, and C_j be the cycle length
: mod p_j^{e_j}. By the Chinese Remainder Theorem, C = lcm(C_1,..,C_n).
:
: Consequently, it suffices to analyze the cycle length of the recurrence
: relation over the rings Z/p^eZ. Classical shift register theory should
: get you the rest of the way, I suspect -- or at least, for the e=1 case.
: See, e.g., Golomb's treatise.
:
: (Does anyone know if the e>1 case has been studied? Or does Hensel
: lifting make the e>1 case follow easily from the e=1 case, or somesuch?)
:
: To give you a taste of classical shift register theory, we will probably
: want to look at the polynomial
: f(x) = x^b + x^{b-1} + 1 in (Z/p^eZ)[x]:
: e.g., is it irreducible, primitive, and so on. More generally, if I'm
: not mistaken, the cycle length mod p^e should divide the order of x in
: (Z/p^eZ)[x]/(f(x)), I think. But please check these claims carefully for
: yourself -- they're off the top of my head, and I'm not too terribly good
: at shift register theory, so I might have gotten important facts wrong.
:
: In the special case where b=10, we write b=2*5, and note that we get
: a linear combination of a 10-bit traditional LFSR over GF(2) and a
: 10-symbol linear shift register over GF(5). Therefore, I'd expect the
: cycle length to be very good, but the security to be potentially very
: low: the LFSR over GF(2) provides very little security, thanks to the
: Berlekamp-Massey cryptanalysis algorithm; I can't imagine the LFSR over
: GF(5) is much better (but I don't know for sure whether Berlekamp-Massey
: generalizes to arbitrary finite fields, offhand).
:
: Hopefully that should be enough to get you started, even if I got some
: of the details slightly wrong. Enjoy!
Thanks very much for all the pointers!
The Berlekamp-Massey algorithm must be very cool. Although I knew
that an LFSR sequence could be used to get good clues about the
initial key, I didn't know there was an actual algorithm to
re-construct it, at least for b=2. (I'm just now reading this on
Terry Ritter's webpage.) And I'm really curious whether it's been
generalized to b>2.
I'd love to just take a look at Golomb's _Shift_Register_Sequences_
but haven't been able to find it yet.
--
r.e.s.
[EMAIL PROTECTED]
------------------------------
Date: Mon, 06 Dec 1999 04:40:33 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: iaPCBC: confidentiality and integrity in one shot (long)
=====BEGIN PGP SIGNED MESSAGE=====
James Muir wrote:
>
> iaPCBC stands for integrity aware plaintext ciphertext block chaining.
> It's been proposed as a new mode of operation for block ciphers. It
> claims to provide data confidentiality and integrity with one
> cryptographic operation. See
>
> http://www.research.att.com/~smb/papers/iapcbc.ps
> http://www.research.att.com/~smb/papers/draft-bellovin-iapcbc-00.txt
>
> for a complete description.
>
> Has anyone analyzed iaPCBC yet? If so, can someone point me to the
> analysis?
I had a look at this, and found a potential avenue of attack (perhaps
somewhat impractical, but I think it's sufficient to show that iaPCBC is
not as strong as the existing IPsec integrity mechanism, HMAC).
Here's the description of the algorithm from draft-bellovin-iapcbc-00,
edited slightly:
# [Assume a cipher with block size B >= 64 bits. Encryption is denoted
# by E(K, P); decryption D(K, P). Keys are N bits.]
#
# The iaPCBC algorithm requires two keys. The first, KD, is used for
# confidentiality of the payload. Per [RFC2401], KD is taken from the
# first N bits of negotiated keying material. The second, KI, is used
# to generate and protect P[0] and C[0]. The next N bits of the
# negotiated keying material are used for KI.
#
# When keys are changed, a new value for R[0] MUST be generated. This
# MUST be a secret, per-key unique number. If a pseudo-random number
# generator is used to produce R[0], it MUST be strongly seeded; i.e.,
# per the suggestions of [RFC1750]. Implementors MAY use extra bits of
# keying material as part of the seed.
#
# The first cipher block contains C[0]; see the description below for
# its generation. C[0] transports, in effect, IV material to the far
# end. C[0] is not encrypted with KD.
#
# The usual ESP packet layout, including padding and the Next Header
# indicator, come next. This is followed by a duplicate copy of the
# SPI [Security Parameters Index] and the packet sequence number,
# padded out with 0-bits if necessary to fill the cipher's block size.
# [snip possible padding variant for block sizes > 64 bits]
# This last block acts as the authentication data; the receiver MUST
# verify that the contents of these fields is as expected.
#
# To encrypt a packet of plaintext blocks P[1..M], arranged as above
# including the duplicate SPI and sequence number, the following
# algorithm is used:
#
# C[0] = E(KI, R[0]);
# P[0] = E(KI, R[0] + 1);
# for (i = 1; i <= M; i++) {
# R[i] = R[i-1] + P[i-1] + C[i-1];
# C[i] = E(KD, R[i] ^ P[i]);
# }
# R[0] = G(R[0]);
#
# All additions used are computed modulo 2^B.
#
# The blocks C[1..M] are the ciphertext. (Note that the above
# algorithm assumes an empty block P[0] before the plaintext.)
#
# The value R[0] is a per-key variable, and [is either retained
# between packets, or a CSPRNG is used to generate a fresh R[0]
# for each packet].
I.e. as a diagram:
<pre>
ADD means addition mod 2^B.
XOR means exclusive or.
P1 P2 PM = SPI, seq#
| | |
+-->ADD 1-->E_KI--+ +----+ +----+ |
| v | v | v |
R0-->-+--------------->ADD->-+---)-->ADD->-+---)-->ADD-> ... ->-+ |
| | ^ | v ^ | v ^ | v
| +------>-----+ | +->XOR | +->XOR | +->XOR
| v | v | v | v
| E_KI | E_KD | E_KD | E_KD
v | | | | | | |
G +----+ +----+ +----+ |
| v v v v
| C0 C1 C2 CM
|
v
R0 for next packet (or generate randomly)
</pre>
# To decrypt a packet of ciphertext blocks C[1..M], the following
# algorithm is used:
#
# R[0] = D(KI, C[0]);
# P[0] = E(KI, R[0] + 1);
# for (i = 1; i <= M; i++) {
# R[i] = R[i-1] + P[i-1] + C[i-1];
# P[i] = D(KD, C[i]) ^ R[i];
# }
#
# All additions used are computed modulo 2^B.
#
# The plaintext will be in P[1..M-1].
#
# Following the decryption, the encrypted copies of the SPI and
# sequence number in block P[M] MUST be compared against the plaintext
# ones; in addition, any constant padding MUST be checked for
# correctness. If any of these checks fail, an integrity failure has
# occurred; this is an auditable event, and must be handled
# appropriately.
Now for the attack. First, note that any integrity mechanism should be
secure even in the case where the plaintext is known by the attacker.
So we can assume that P[1..M] are known (P[M] is a copy of the
SPI and sequence number, which is sent in the clear).
The security of the algorithm depends on the intermediate values R[i]
being secret. If we had the plaintext and a single R[i] for some i >= 1,
then we would have enough information to solve for any R[i], i >= 1
(using R[i] := R[i-1] + P[i-1] + C[i-1] to go forwards in the sequence,
and R[i-1] := R[i] - P[i-1] - C[i-1] to go backwards). We would also
know the inputs and outputs of all the encryptions using KD.
In that case we could forge a message that would pass the integrity check,
as follows:
1. Rearrange the ciphertext blocks in some order, possibly repeating
some blocks and dropping others.
2. Recalculate the plaintext, including the final check block. This
can be done without knowing KD, by making use of the fact that the
block cipher is a fixed permutation (i.e. the rearranged ciphertext
blocks will decrypt to the same values that they decrypted to in
the original packet).
3. Repeat from step 1 until a favourable plaintext and final block
is found.
4. [For IPsec] Resend the packet, with an SPI and sequence number
taken from the new final block (the SPI would have to correspond to
the same key as before).
Breaking iaPCBC by this method therefore boils down to finding an
intermediate R[i] value.
Suppose that, by coincidence, a ciphertext block repeats within a
single packet (i.e. C[i] = C[j] for i < j). The probability of this
happening is small, but not insignificant, at least for 64-bit
blocks (especially if we are comparing iaPCBC to HMAC, which seems
to be able to handle very large amounts of data without any security
problem). Also note that for applications of iaPCBC other than
IPsec, the message may be of arbitrary length.
Anyway, assuming that a ciphertext block is repeated, the corresponding
inputs to the block cipher will also be equal:
R[i] XOR P[i] = R[j] XOR P[j]
Let X = sum[k = i..j-1](P[k] + C[k]) (using mod 2^B addition)
- From the definition of the sequence R, we have
R[j] = R[i] + X
Substituting for R[j],
R[i] XOR P[i] = (R[i] + X) XOR P[j]
Let Y = P[i] XOR P[j], then
R[i] XOR Y = R[i] + X, where X and Y are known.
XOR and addition are very similar, but the difference in the treatment
of carry allows us to solve for some of the bits of R[i]. Let the suffix
"_k" denote bit k of any value (numbering from 0 for the least significant
bit).
Bit 0: R[i]_0 XOR Y_0 = R[i]_0 XOR X_0
(this doesn't help much)
Bit 1: let C_1 = R[i]_0 AND X_0 (carry from previous bit)
R[i]_1 XOR Y_1 = R[i]_1 XOR X_1 XOR C_1
C_1 = R[i]_0 AND X_0 = X_1 XOR Y_1
therefore if X_0 = 1, we know that R[i]_0 = X_1 XOR Y_1
if X_0 = 0, we gain no information
["a ? b : c" is the boolean conditional operator,
"if a is true then b, otherwise c"]
Bit 2: let C_2 = C_1 ? (R[i]_1 OR X_1) : (R[i]_1 AND X_1)
R[i]_2 XOR Y_2 = R[i]_2 XOR X_2 XOR C_2
if C_1 = 1, then C_2 = R[i]_1 OR X_1 = X_2 XOR Y_2
therefore if X_1 = 0, we know that R[i]_1 = X_2 XOR Y_2
if X_1 = 1, we gain no information
if C_1 = 0, then C_2 = R[i]_1 AND X_1 = X_2 XOR Y_2
therefore if X_1 = 1, we know that R[i]_1 = X_2 XOR Y_2
if X_1 = 0, we gain no information
and so on. After generalising this for any bit position and then
simplifying, we end up with:
R[i]_k = { X_{k+1} XOR Y_{k+1}, if Y_k = 1
{ unknown, otherwise
for k = 0..B-2 (R[i]_{B-1} is always unknown).
If all bits of Y (which is the XOR of two plaintext blocks) are random and
unbiased, the attacker will find on average (B-1)/2 of the bits of R[i].
For a chosen plaintext attack, the attacker could arrange that the
plaintext consists of only two blocks that are complements of each other,
and are repeated about the same number of times, so that with probability
1/2 Y would be all ones, and all of the bits of R[i] would be retrieved.
In conclusion, and assuming I haven't made a mistake, iaPCBC does not
guarantee integrity for messages that have a repeated ciphertext block.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
"Attempts to control the use of encryption technology are wrong in principle,
unworkable in practice, and damaging to the long-term economic value of the
information networks." -- UK Labour Party pre-election policy document
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOEsrOjkCAxeYt5gVAQHJvwf+O0qOXXcAG/Ygj8dXjYRn4d5XVZvlz2pi
bqnuQcer79Zrbm0coiRjxn58/AgY24VKxKWFhCNKXQjfSYy4cnlVauTT7TcGDIwe
LmeNDNFyX+XYIQ1Mg28EF0KHfKNLoPI0ttcLSI9QbPb9akIn1bAl/pR2vwLPDLQe
J67FkreB++Mj0zk/zBhCeXGzM4yQ6Flp1wa3njppkB1euYlfCRrd3CPEMRoeOsQa
aLJ+/6bhzStOWlPUer99l5Q5tyAjk5T4L3Yq2B/VhNbpMY1gBXWcBL7oRXNLMnHU
wccLQi3iWweY1IWzaSnGi1s34PSFqu4n5pO9877Yy/sOQKe7/bQg0A==
=5SMN
=====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
******************************
