Cryptography-Digest Digest #466, Volume #13 Sat, 13 Jan 01 21:13:01 EST
Contents:
Is this triple-DES variant secure? (Kenneth Almquist)
Re: Big block DES construct. (Benjamin Goldberg)
Re: Is this triple-DES variant secure? (Benjamin Goldberg)
Re: Security proof (Benjamin Goldberg)
Re: On cryptographic proofs and their (lack) of concreteness (Terry Ritter)
Yet another cipher idea (Benjamin Goldberg)
Re: The Word Problem and Group Isomorphism ("John A. Malley")
Re: NSA and Linux Security (Greggy)
Re: Security proof (David Wagner)
Re: Security proof (David Wagner)
Re: The Word Problem and Group Isomorphism (David Wagner)
Re: Is this triple-DES variant secure? (David Wagner)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Is this triple-DES variant secure?
Date: 13 Jan 2001 20:54:58 GMT
If triple-DES is used in CBC mode, then it is not possible to pipeline
the process because the output of one triple-DES encryption must be
xor-ed with the input to the next triple-DES encryption. An alternative
is to xor each intermediate encryption values with the preceding
intermediate value. The following pseudocode shows what I mean:
temp := E(P[i], K1) xor F1[i]
F1[i+1] := temp
temp := E(temp, K2)
F2[i+1] := temp
C[i] = E(temp xor F2[i], K1)
In this code,
E(text, key) is DES encryption,
D(text, key) is DES decryption,
P and C are the plaintext and cyphertext, respectively,
K1 and K2 are DES keys which together form the triple-DES key,
and F1 and F2 are feedback variables.
This can be pipelined very deeply. The dependency between pipeline stages
is that an xor operation must be performed to compute F1[i+1] from F1[i].
If the time required by this xor (and associated wiring delays) is 1/4
of the time required for a DES round, we could create a 192 stage pipeline
resulting in very high throughput.
High throughput is no good if the encryption can be broken. In fact, the
above scheme is vulnerable to the following chosen plaintext attack. We
start by guessing the value of K1. To see if we have guessed correctly,
we set P[i] = P[i+1] = D(0, K1). Then F1[i+1] = F1[i], so F2[i+1] = F2[i].
Therefore C[i+1] = E(F2[i+1] xor F2[i], K1) = E(0, K1). If this last
equation holds, then we have almost certainly guessed K1 correctly.
There are 2**56 possible values for K1, and since triple-DES works on
64 bit blocks, the cypher is presumably rekeyed every 2**32 blocks.
Since it takes two blocks to check a guess for K1, we would expect to
get a match about once every 2**57 blocks, meaning we recoved one K1
value for every 2**25 keys. Getting the value of K2 is a problem if
we don't know F1 and F2, but perhaps a differential attack could get
us K2 in fewer than 2**112 steps.
To avoid this chosen plaintext attack, I propose swapping K1 and K2
on alternate rounds. In pseudocode, this looks like:
temp := E(P[i], K1) xor F1[i]
F1[i+1] := temp
temp := E(temp, K2)
F2[i+1] := temp
C[i] = E(temp xor F2[i], K1)
temp := E(P[i+1], K2) xor F1[i+1]
F1[i+2] := temp
temp := E(temp, K1)
F2[i+2] := temp
C[i+1] = E(temp xor F2[i+1], K2)
A variant of the previously described attack could be used against this
construct, but it would require guessing *both* K1 and K2, so it would
have no advantage over an exhaustive search. Can anyone suggest another
way to attack this construct?
Kenneth Almquist
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Big block DES construct.
Date: Sat, 13 Jan 2001 21:28:44 GMT
Whaa (boo hoo)! Looking around, I discovered the page
http://www.io.com/~ritter/NEWS/LBDNEWS.HTM
and learned that the 2x2 DES construct I gave is indeed susceptible to
meet-in-the-middle attacks.
However, although Nx2 DES can be attacked by MIM, Nx3 DES seems not to
be susceptible. However, since Nx3 DES is no faster than 3DES, there
does not seem to have been any more research on that construct.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Is this triple-DES variant secure?
Date: Sat, 13 Jan 2001 21:45:41 GMT
Kenneth Almquist wrote:
>
[snip]
> The following pseudocode shows what I mean:
>
> temp := E(P[i], K1) xor F1[i]
> F1[i+1] := temp
> temp := E(temp, K2)
> F2[i+1] := temp
> C[i] = E(temp xor F2[i], K1)
>
> In this code,
> E(text, key) is DES encryption,
> D(text, key) is DES decryption,
> P and C are the plaintext and cyphertext, respectively,
> K1 and K2 are DES keys which together form the triple-DES key,
> and F1 and F2 are feedback variables.
There is a problem with how this psuedocode is written. You should
avoid using and reusing a thing like "temp." A better way to write this
would be:
F1[i+1] := E(P[i], K1) xor F1[i]
F2[i+1] := E(F1[i+1], K2)
C[i] := E(F[i+1] xor F2[i], K1)
[snip]
>
> To avoid this chosen plaintext attack, I propose swapping K1 and K2
> on alternate rounds. In pseudocode, this looks like:
>
> temp := E(P[i], K1) xor F1[i]
> F1[i+1] := temp
> temp := E(temp, K2)
> F2[i+1] := temp
> C[i] = E(temp xor F2[i], K1)
>
> temp := E(P[i+1], K2) xor F1[i+1]
> F1[i+2] := temp
> temp := E(temp, K1)
> F2[i+2] := temp
> C[i+1] = E(temp xor F2[i+1], K2)
Again, use of "temp" makes this harder to analyse than it should be.
Here's a rewrite:
1) F1[i+1] := E(P[i], K1) xor F1[i]
2) F2[i+1] := E(F1[i+1], K2)
3) C [i] := E(F2[i+1] xor F2[i], K1)
4) F1[i+2] := E(P[i+1], K2) xor F1[i+1]
5) F2[i+2] := E(F1[i+2], K1)
6) C [i+1] := E(F2[i+2] xor F2[i+1], K2)
It becomes much easier to see that step 4 can be done right after 1, and
5 done right after 2, and 6 done right after 3, without worrying about
which "temp" belongs to which computation.
> Can anyone suggest another way to attack this construct?
I'm not entirely certain, but one might consider that the middle step of
3DES is a decrypt, and the first and third are encrypts. Surely there's
a reason for this, and perhaps that reason applies.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Security proof
Date: Sat, 13 Jan 2001 22:22:44 GMT
Benjamin Goldberg wrote:
[snip]
>
> Notation:
> Let M be an SPRP, and M(K) is a particular 2N bit permutation.
> Let a, b, c, d each be 1/4 of the 4N bit plaintext.
> Let w, x, y, z each be an N bit temp variable
> Let e, f, g, h each be 1/4 of the 4N bit ciphertext.
>
> The reduced size cipher is as follows:
> (w, x) = M(K0)(a, b)
> (y, z) = M(K1)(c, d)
> (e, f) = M(K2)(w, y)
> (g, h) = M(K3)(x, z)
This is insecure since a meet-in-the-middle attack works on it.
However, for the 8N variant, no meet-in-the-middle attack should be
possible.
Let M be an SPRP, and M(K) is a particular 2N bit permutation.
Let p_(0..7) each be 1/8 of the 8N bit plaintext.
Let t_(0..7) each be an N bit temp variable
Let c_(0..7) each be 1/8 of the 8N bit ciphertext.
(t0, t1) = M(K0)(p0, p1)
(t2, t3) = M(K1)(p2, p3)
(t4, t5) = M(K2)(p4, p5)
(t6, t7) = M(K3)(p6, p7)
(t0, t2) = M(K4)(t0, t2)
(t1, t3) = M(K5)(t1, t3)
(t4, t6) = M(K6)(t4, t6)
(t5, t7) = M(K7)(t5, t7)
(c0, c4) = M(K8)(t0, t4)
(c1, c5) = M(K9)(t1, t5)
(c2, c6) = M(KA)(t2, t6)
(c3, c7) = M(KB)(t3, t7)
Is it possible to prove, that if M is a SPRP, that this construct is
also an SPRP? No MIM attack is possible on this. I want to write a
proof that says as much about this kind of construct as Luby and
Rackoff's proof said about Feistels. They proved that an N round (N>=3)
Feistel is a PRP if F is a PRF. I want to prove that an order N FFT
mixer, with an SPRP as a mixer, is an SPRP.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: On cryptographic proofs and their (lack) of concreteness
Date: Sat, 13 Jan 2001 22:34:26 GMT
On Fri, 12 Jan 2001 15:18:31 -0800, in <Oyy2E4OfAHA.275@cpmsnbbsa07>,
in sci.crypt "Joseph Ashwood" <[EMAIL PROTECTED]> wrote:
>[...]
>While the proofs are not of the form, therefore this is provably secure,
>they are of great use, and the maintainance and examination of the
>primitives and protocols is far less costly. I depend on this kind of proof
>every day, some are obvious, some are not, but if my judgement is ever
>called into question, I can justify myself.
Proofs can be helpful, but they can also mislead, and do so in a way
which is difficult to confront or correct. I also see a problem in
the casual misuse of the deceptive phrase "proven secure" absent
caveats and limitations.
We have all seen repeated newbie examples of the claim that a
one-time-pad is the only provably secure cipher -- but of course that
proof only applies in practice if one can first *prove* the keying
sequence is unpredictable, which is generally impossible. Surely
nobody believes that a proof will somehow make a predictable sequence
strong, or cause it to protect data mixed only by XOR.
Also, nobody should think that we can measure the unpredictability of
an arbitrary sequence. It is not unusual for the detailed analysis of
a supposedly-random sequence to reveal level after level of structure
and -- to some extent -- predictability. One is generally forced to
*hope* that the predictability is insufficient to expose data, but
hope is a long, long way from proof.
The theoretical sort of "proven security" is peculiar anyway: If the
proof only applies to a theoretical system, exactly what kind of
"security" could be at risk? I find it hard to imagine the term
"security" applying to theoretical data, since nothing really exists
which can be either lost or protected. Surely one would expect the
unmodified term "security" to mean the protection of something real.
But if "security" *does* apply to real data, in what way has the OTP
ever proven secure in any sense at all? There is not now and never
has been any way to measure the unpredictability of an arbitrary
sequence. Unpredictability is not the same as measurable entropy.
None of this means that OTP's are insecure, of course; it just means
that practical OTP's are *potentially* insecure, like every other
cipher. But it also means the "proof" part of this has been wholly
misleading to a great many people for a very long time.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Yet another cipher idea
Date: Sat, 13 Jan 2001 23:48:55 GMT
Since this cipher idea depends on bit manipulations, I'll assume that it
will only be done in hardware, if at all.
The concept: Make 8x8 matrix, and put one bit in each. Encipher each
row with a secure 8 bit PRP. Then transpose rows and columns.
Three rounds are needed to prevent a MIM attack.
Three rounds are also needed for SAC.
Here's how avalanche happens:
Assume that ANY change going into a block flips approximatly half the
bits when coming out of that block.
Round (1) A 1 bit change going into round 1 will change 4 bits, on
average coming out of round one. Each of these 4 bits becomes a 1 bit
change going into the next round, each in a different block.
Round (2) a 4 bit change going into round 2 (each bit in one block)
becomes a 16 bit change, on average, coming out.
Round (3) Since there are only 8 blocks, odds are, going into round 3,
there will be a change going into each and every block.
Thus, a one bit change in the plaintext results in about half of the
bits ciphertext changing.
Aside from the fact that a 64 bit blocksize is much too small, does
anyone see any attacks on this?
Not that I would actually use it... But I'm interested in what kind of
information proofs might be made about its security, if the strength of
the PRP is assumed.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: The Word Problem and Group Isomorphism
Date: Sat, 13 Jan 2001 16:11:23 -0800
Ben Hopson wrote:
>
> Sorry I screwed up the date before. OS problems...
>
> Forgive me as I am an outsider. Does anyone know of cryptosystems based on
> the undecidability of the word problem? (ie the difficulty in identifying
> the groups generated by relations).
>
"A public key cryptosystem based on the word problem", N. R. Wagner and
M. R Magyarik, Advances in Cryptology
Proceedings of Crypto '84, Edited by G. R. Blakley and David Chaum.
I haven't read the paper but I know of its existence - hope this helps
your search.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: NSA and Linux Security
Date: Sun, 14 Jan 2001 01:19:23 GMT
> The intelligence agencies are still accountable to the government.
Oversighted? Like the drug dealers oversighted by the mob...
> ...and the government of the USA is acting in the best
> interests of the citizens of the USA.
Like Janet Reno saying, "we had to act for the children" when they
rolled the children over with tanks?
> > What the hell do you mean, "What about it?" You sound
> > like violating the privacy of citizens is fine with you!!!
>
> Well, it's certainly fine with me.
Then what's next? Shall they enter our homes without a warrant? Where
do you draw the line? Your idea of life is scary.
> The auto-scanning of my e-mails,
> phone calls, SMS messages, whatever, etc. from, say, Menwith Hill,
> isn't going to provide my government (or the overbearing US one) with
> any interesting titbits of valuable information.
That was never the issue, now was it?
> > > Echelon is designed to catch the stupid criminal who thinks e-mail
> > > is secure & safe.
> > I don't believe you are naive to believe that lame excuse.
> It's true though. Put it this way, do you think that someone is
sitting
> at a desk somewhere actively listening to the phone calls of every
> citizen or reading every email? If so, you must lead a happy life -
> only willing to talk to people on the street in encrypted language in
> case Big Brother is watching, etc. and encrypting every single email,
> SMS message, etc etc using one-time pads. Oh wait, these posts aren't
> encrypted are they? We've given them free info! Argh! Eeek!
Let me say it very clearly to keep your focus on what I replied to.
The quote is above and has to do with what Echelon was designed for.
It is not designed to catch bad guys. It is designed to have in place
for the day that those corrupt in government want to abuse those they
govern. The cover is to catch the bad guy. Privacy advocates don't
mind so much that something like that is in place, but that it is in
the hands of those who could become so corrupt that when they no longer
answer to anyone then great tyranny can abound. While your vision is
limited to the present, ours is wide open to the posibilities that such
a system affords those who under the cover of secrecy may want to use
such powers against their political enemies. And no doubt you are so
blind to the IRS that you would say that such things simply don't
happen.
> > That's like the one, "The truth about JFK's assassination must
> > be kept from the people of America for national security reasons."
> Elvis is still alive too...
It is simply obvious that the government lied. End of statement. Your
reference to Elvis is a character assassination shot. I quit this
conversation, pal.
> > > But of course, because the 'criminal' actions are covered up you
> > > have no evidence to back up these claims.
> >
> > Oh, come on! You aren't that naive!
>
> What's naive? How can the average joe on the street have any
> substantial evidence that would hold up in court against the NSA?
>
> National security, as a case, would win regardless.
Sovereign emunity wins at Ruby Ridge. What of it?
Your arguments sound good but are easy to dismantle, given the time and
I have run out of patience...
--
I prefer my fourth amendment rights over a dope free
society, even if the latter could actually be achieved.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Security proof
Date: 14 Jan 2001 01:50:05 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Benjamin Goldberg wrote:
>Notation:
>Let M be a SPRP, and M(K) is a particular 2N bit permutation.
>Let a, b, c, d each be 1/4 of the 4N bit plaintext.
>Let w, x, y, z each be an N bit temp variable
>Let e, f, g, h each be 1/4 of the 4N bit ciphertext.
>
>The reduced size cipher is as follows:
>(w, x) = M(K0)(a, b)
>(y, z) = M(K1)(c, d)
>(e, f) = M(K2)(w, y)
>(g, h) = M(K3)(x, z)
>
>How do I go about proving that this construct is also an SPRP?
You don't -- it's not a SPRP. :-)
Choose a,b,c,d,c',d' arbitrarily, where (c,d) != (c',d').
Let (e,f,g,h) be the encryption of the plaintext (a,b,c,d).
Let (e',f',g',h') be the encryption of the plaintext (a,b,c',d').
Finally, obtain the decryption of (e,f,g',h'). Note that for your
cipher, this third plaintext will be of the form (a,b,?,?), where ?
represents an unknown word.
For a true SPRP, you wouldn't be able to predict anything about
the third plaintext. Hence, your construction is not a SPRP.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Security proof
Date: 14 Jan 2001 01:57:06 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Benjamin Goldberg wrote:
> (t0, t1) = M(K0)(p0, p1)
> (t2, t3) = M(K1)(p2, p3)
> (t4, t5) = M(K2)(p4, p5)
> (t6, t7) = M(K3)(p6, p7)
>
> (u0, u2) = M(K4)(t0, t2)
> (u1, u3) = M(K5)(t1, t3)
> (u4, u6) = M(K6)(t4, t6)
> (u5, u7) = M(K7)(t5, t7)
>
> (c0, c4) = M(K8)(u0, u4)
> (c1, c5) = M(K9)(u1, u5)
> (c2, c6) = M(KA)(u2, u6)
> (c3, c7) = M(KB)(u3, u7)
[Note: I changed your notation slightly.]
That's not a SPRP, either.
Let c0,..,c7 be the encryption of an arbitrary plaintext p0,..,p7.
Let c0',..,c7' be the encryption of a plaintext p0,..,p6,p7' differing
from the first plaintext only in the last word.
Now, consider the decryption of the ciphertext
c0,c1',c2,c3',c4,c5',c6,c7'.
This third plaintext will have the form p0,..,p5,?,?.
Since for a real SPRP we would not be able to predict anything about
the third plaintext, your construction must not be a SPRP.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: The Word Problem and Group Isomorphism
Date: 14 Jan 2001 02:02:06 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Ben Hopson wrote:
>Does anyone know of cryptosystems based on the undecidability of
>the word problem?
I don't know of any cryptosystem whose security is based on the
undecidability of any problem whatsoever.
It is unclear to me how an undecidability result could be used
in cryptography. The problem is that encryption algorithms are
necessarily based on a decidable problem: Anyone who has the key
has to be able to decrypt, hence any attacker who can guess the
key can confirm his guess and recover the plaintext (assuming the
plaintext is much longer than the key). This all seems to mean
that there is an algorithm (albeit a slow one) for breaking any
realistic encryption system: Simply try decrypting the ciphertext
under each possible ciphertext, until you get something that looks
like plaintext. This terminates.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Is this triple-DES variant secure?
Date: 14 Jan 2001 02:06:04 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
This is known as inner chaining, and Eli Biham has shown reasons
to believe that it is likely to be less secure than outer chaining.
Take a look at the following papers:
Eli Biham, ``On modes of operation'', FSE'93.
http://www.cs.technion.ac.il/~biham/Reports/onmodes.ps.gz
Eli Biham, ``Cryptanalysis of multiple modes of operation'', ASIACRYPT'94.
http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-get.cgi/1994/CS/CS0833.ps
------------------------------
** 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
******************************
