Cryptography-Digest Digest #902, Volume #12 Thu, 12 Oct 00 05:13:01 EDT
Contents:
What was solution to Stage 5 of The Code Book Challenge? (UBCHI2)
Re: A new paper claiming P=NP (Virgil)
Triple DES versus Rijndael (UBCHI2)
Re: What was solution to Stage 5 of The Code Book Challenge? (Staffan Ulfberg)
Is it trivial for NSA to crack these ciphers? (Anonymous)
Re: A new paper claiming P=NP (Eric Lehman)
Re: Triple DES versus Rijndael (Roger Schlafly)
Re: A new paper claiming P=NP (Bill Unruh)
Re: Rijndael test vectors ("Brian Gladman")
Re: On block encryption processing with intermediate permutations (David Hopwood)
Re: A new paper claiming P=NP (Mike ROBSON)
Re: Rijndael test vectors ("Brian Gladman")
Re: A5/1 attack implementation? (Thomas Pornin)
Re: Is it trivial for NSA to crack these ciphers? ("Douglas A. Gwyn")
Re: What is meant by non-Linear... ("Rob Marston")
Playfair Cipher Decoders... ("Rob Marston")
Re: Is it trivial for NSA to crack these ciphers? (Andre van Straaten)
Re: On block encryption processing with intermediate permutations (Bryan Olson)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: What was solution to Stage 5 of The Code Book Challenge?
Date: 12 Oct 2000 04:36:32 GMT
What was the encryption technique used in stage 5 of the cipher challenge of
Simon Singh?
------------------------------
From: Virgil <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Wed, 11 Oct 2000 22:47:22 -0600
In article <[EMAIL PROTECTED]>, Paul Rubin
<[EMAIL PROTECTED]> wrote:
> Anyway, getting away from the digression on what P and NP are and how
> to convert postscript to pdf, there's a discussion thread on Slashdot
> about this paper and it sounds like a false alarm. Someone over there
> who seemed to know what he was doing started reading it, and found
> enough mistakes in the first few pages that he didn't feel it necessary
> to bother reading further.
>
What was the author of the paper claiming P=NP. Is it anyone we know?
------------------------------
From: [EMAIL PROTECTED] (UBCHI2)
Subject: Triple DES versus Rijndael
Date: 12 Oct 2000 04:47:58 GMT
How do the two ciphers compare in terms of ease in implementation and security?
------------------------------
Subject: Re: What was solution to Stage 5 of The Code Book Challenge?
From: Staffan Ulfberg <[EMAIL PROTECTED]>
Date: Thu, 12 Oct 2000 04:47:27 GMT
[EMAIL PROTECTED] (UBCHI2) writes:
> What was the encryption technique used in stage 5 of the cipher challenge of
> Simon Singh?
Stage 5 is a book cipher. The numbers are indices of characters or
words in a widely available text. To decode the message, replace each
number by the corresponding character (or initial character if you are
counting words.)
The solution is available at http://answers.codebook.org (See the PDF
or PostScript version of the report; Stage 5 is missing from the HTML
version for some strange reason.)
Staffan
------------------------------
Date: 12 Oct 2000 05:56:13 -0000
From: Anonymous <[EMAIL PROTECTED]>
Subject: Is it trivial for NSA to crack these ciphers?
I'm not really interested in opinions of the relative strengths/weakness of various
ciphers.
I'm more interested to know what people think about NSA's ability to break messages
encrypted with these ciphers.
Which ciphers?
How about any of the AES finalists?
It seems to me that it wouldn't be out of the question for the FBI to get access to
encryption breaking facilities at Ft. Meade if the believed there was significant risk
to "national security".
So what I'm trying to say is, if the FBI can break this stuff, it's pretty useless
isn't it?
The Russians don't want the NSA reading their message traffic. What the hell do they
use?
Thanks in advance. I hope no one thinks I'm a troll.
------------------------------
From: Eric Lehman <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Thu, 12 Oct 2000 06:06:31 GMT
[After this, I'll only post to comp.theory.]
> Otherwise, please
> don't refer to such non-scientific sources as slashdot
GET REAL! Why has this paper not been submitted somewhere other than
your *WEBSITE*??? What about STOC, FOCS, or even ECCC? The approach in
this paper is reasonable on its face, but its handling is definitely
out-of-channel. Some would even say... KOOKY. What's the story? Is
the author a friend of yours?
Please understand that this paper is nearly unintelligible. Almost
every sentence contains at least one grammatical or punctuation error (I
do *not* exaggerate), and there appear to be mathematical slips as
well. For example, even the little 3-step algorithm on pages 5-6 seems
to have an indexing error. In particular, N must decrement n times for
the procedure to terminate, but by then variable i could easily exceed
n, which is nonsensical. Am I overlooking something?
Given this mess, I doubt the paper will ever be verified or refuted
without someone to answer detailed questions on the text. You've
decided to widely popularize the paper; will you take on this
clarification task for us?!
The rest of this post concerns details of the paper. Here's where I'm
stuck:
On page 10 he shows how to direct the edges of a graph G to get a DAG,
which defines a poset. Fine. Take a minimum chain decomposition.
Fine. Now we get definitions:
A path P in G is said to be "stretched" on the set of chains that it
intersects. Is this correct?
The definition of "densely stretched" confuses me. A path P in G is
said to be "densely stretched" on the set of chains it intersects
*provided* no two adjacent vertices on the path lie in the same chain.
Is this correct? Or is it that no two vertices connected by an edge in
G can lie in the same chain? As I understand it, every simple path is
"stretched" on some set of chains, but not every simple path is "densely
stretched" on some set of chains. Correct?
Then I get down to this: "It is easy to see that a simple undirected
path of the length L can be densely stretched on not less than
ceil(L/2)+1 paths of P..." Where are the quantifiers in this
assertion? Is he making a statement that holds FOR EVERY poset that can
be generated from a graph G by his procedure, EVERY minimum chain
decomposition, and EVERY path of length L in G? And what's with the
"can be" in here?
To clarify matters, can you explain his assertion with regard to the
following example? Suppose I take graph G itself to be a simple path of
length 6. Then I obtain a poset from G as follows. First, I pick every
other vertex and form one maximal independent set. Then I pick the
remaining vertices to form a second maximal independent set. This gives
me a poset with a Hasse diagram like this:
/\/\/
Now the minimum chain decompsition is unique and consists of the three /
chains. Let's consider the simple path consisting of the entire graph
G. Now it seems that is is not densely stretched on ANY set of chains,
because adjacent vertices lie in the same chain. I'm lost...
/Eric
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Triple DES versus Rijndael
Date: Wed, 11 Oct 2000 23:16:34 -0700
UBCHI2 wrote:
> How do the two ciphers compare in terms of ease in implementation and security?
Both are fine for most purposes. Rijndael has some security
advantages -- mainly that it uses a 128-bit block instead
of 64-bit block. Rijndael is also a little easier to
implement from scratch, but most people will build on
someone else's implementation anyway, so I am not sure that
is much of a factor.
Triple DES has stood the test of time. No need to use Rijndael
until it is the definite AES.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 12 Oct 2000 06:45:10 GMT
In <8s29vn$ll8$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Jonathan
Thornburg) writes:
>And last but not least, in place of acrobat's ##$@!@#$%^&* annoying spash
>screen, xpdf just prints an annoying copyright message to stdout... so
>a 3-line shell script can filter it out to achive "silent" operation.
Actually my version (.91 on Mandrake 7.1) does not print out anything--
just opens the window.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Rijndael test vectors
Date: Thu, 12 Oct 2000 08:12:09 +0100
"David Hopwood" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Roger Schlafly wrote:
> > Brian Gladman wrote:
> > > Welcome to the endian world of AES!
> > > A world I hope we can remove by getting the specification right on
> > > such matters.
> >
> > Yes. I once implemented DES based on the spec, and then discovered
> > that others used the bits in a different order. It seems the
> > official spec talked about bits, but not bytes, leaving the
> > order of bits in a byte ambiguous.
>
> I was going to say that the Rijndael spec is clear about bit and
> byte ordering, but on closer examination it never explicitly says that
> the mapping of the key bytes to words follows the same convention as
> the plaintext/ciphertext bytes (although that's obviously supposed to
> be the case).
>
> It would also be better to define explicitly how the bits b_0 to b_7
> map to byte values in section 2.1, i.e.:
>
> _7_
> byte(b_0, .. b_7) = \ (b_i * 2^i)
> /__
> i=0
>
> rather than relying on the example to make this clear.
>
> - --
> 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
>
> iQEVAwUBOeT95DkCAxeYt5gVAQHAKQgAnzqcPjhPdgGrDXowCczr/7OOLj+nltmc
> xeiMgcty+lI8zETbz9nYFSf8k4Q6CLBvQGwWbybVJGELJWrSv1k5svfCUB8xHalu
> Ei9p+vnI8AjXyOQvQ6nKEw/KCe9Lns0lEMS/THysCG4b2iaz9/11v4R+paiJ4eHr
> c7EzGXCmutEw+jPyqWO5vwCLYjl860rIv9jMFm5KxUGPib5q8GxHuaBkxlwkP5bH
> qvc8aqfol2ksz18QzMVLM01rt//Dxc1qotV/JBSMEPYhVzqiV6TFI2oGzKR1xWmC
> uPf6dABYiQ3BsNCGEgbAOIilNyGNULajlDheYdVC4ZyNxSlRIoKpeg==
> =0L3P
> -----END PGP SIGNATURE-----
------------------------------
Date: Thu, 12 Oct 2000 05:45:44 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: On block encryption processing with intermediate permutations
=====BEGIN PGP SIGNED MESSAGE=====
Mok-Kong Shen wrote:
> John Myre wrote:
> > Mok-Kong Shen wrote:
> > <snip>
> > > If I prove a theorem and there is a weakness, say, it depends
> > > on the existence of a quantity p being prime and someone
> > > points out that in a degenerate case p can be 1 and hence
> > > the proof is invalid and I do a little modification such
> > > that this case can be avoided and a prime p still can be
> > > chosen, then my purpose of establishing the theorem is
> > > achieved, isn't it?
> > <snip>
> >
> > Of course not.
> >
> > There is no reason to suppose that the weakness pointed out
> > is the only weakness. Do you also presume, when you fix a
> > bug in a program, that you have now proven it correct?
>
> I was asking in my orignal post for comments for the
> very purpose of enabling me to know the weakness(es).
> Now Bryan Olson claimed to have found an attack and
> subsequently he said that under a certain condition
> his attack doesn't work. So I modified my scheme to
> make it immune to his attack.
No you didn't. It's clear that the attack still applies, although
it is more difficult because the attacker would have to break twice
as many rounds of the cipher as in the original case. Under
reasonable assumptions, it would still be easier than breaking the
cipher in a standard mode such as CBC, though.
The point is that you should be trying to extend the attack
yourself, not making a minor change and relying on others to
cryptanalyse it. You won't learn anything that way.
- --
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
iQEVAwUBOeURgDkCAxeYt5gVAQFAFAf9HowxbVYKIvz966Z/OGWyZUBB6w3rQPVG
pekwH25aJqRWiVmq6m6Rs5eEplS+qRVHCV35g9d1LY7lITD782pZGMBewFqzQcA3
tRO8h9ysTeTuQ+qb5+ETomoqh8uXkmStd6BaPUD02NP4XrCBoIEjs8anqAhKYEi/
wFWivUcbU1a9Xqcbb80LR6rLPV3T9PpUzqqISG99GLqt+cQVk4Ffu2MPSnufkIca
VrjYhVwaIji5+GupsVA3yVYNW2JHLd/uQ+YM8aTiDifAD3Iyat6uqZWwzhF8UoK0
E1SQQFcVhs4pD75dmu2oZKLXRKPaoMYCbs5FHwW+b9LEOI3RTv3Ijw==
=OKdB
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (Mike ROBSON )
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 12 Oct 2000 08:00:36 GMT
On Wed, 11 Oct 2000 10:52:41 -0700, David Eppstein <[EMAIL PROTECTED]> wrote:
>In article <8s2891$4ad$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>(Bill Unruh) wrote:
>
>> >>There's an important technicality you're forgetting: the size of the
>> >>proof might not be polynomial in the size of the original problem.
>>
>> Actually this makes no sense. Proofs do not come in sequences of longer
>> and longer statements of the proof. Also if checking he proof is P, and
>> since cheching is a linear traversal at least of the parts of the proof,
>> then if the size is not P then the checking is not P. So, either way, I
>> do not understand your caveate.
>
>The definition of a problem being in NP is that every yes-instance has a
>witness *of polynomial size* which can be checked in polynomial time.
>Lots of problems in harder complexity classes have witnesses which can be
>checked in P, but the witnesses are too big.
>
>For example, think about your favorite exp-time hard game, such as Chess or
>Go. One possible way to prove you have a winning position would be to
>write down a complete strategy tree -- if he moves there I move there etc
>-- all the way out to checkmate. If someone hands you a strategy tree,
>it's easy to check that the leaves really are checkmate, that each interior
>position lists all legal moves for the opponent, and that each of your own
>moves is legal -- so checking a tree is polynomial time. But the size of
>the tree is exponential in the size of the original game position.
>--
>David Eppstein UC Irvine Dept. of Information & Computer Science
>[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
Actually it's double exponential if you really want a tree.
You can have a strategy DAG with merely exponential size.
Mike Robson.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: Rijndael test vectors
Date: Thu, 12 Oct 2000 08:32:43 +0100
"David Hopwood" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> -----BEGIN PGP SIGNED MESSAGE-----
>
> Roger Schlafly wrote:
> > Brian Gladman wrote:
> > > Welcome to the endian world of AES!
> > > A world I hope we can remove by getting the specification right on
> > > such matters.
> >
> > Yes. I once implemented DES based on the spec, and then discovered
> > that others used the bits in a different order. It seems the
> > official spec talked about bits, but not bytes, leaving the
> > order of bits in a byte ambiguous.
>
> I was going to say that the Rijndael spec is clear about bit and
> byte ordering, but on closer examination it never explicitly says that
> the mapping of the key bytes to words follows the same convention as
> the plaintext/ciphertext bytes (although that's obviously supposed to
> be the case).
>
> It would also be better to define explicitly how the bits b_0 to b_7
> map to byte values in section 2.1, i.e.:
>
> _7_
> byte(b_0, .. b_7) = \ (b_i * 2^i)
> /__
> i=0
>
> rather than relying on the example to make this clear.
Quite a lot was done between version 1 and version 2 of the specification to
get this right but I agree that it is still not perfect.
There has been a long standing issue throughout all the AES cipher
specifications on whether to use bit/byte address order or bite/byte
significance as a primary feature in specification.
For example, some specifications in which bits within a byte are numbered
from 0 to 7 (with bit 0 representing 2^0 = 1) set the byte out on paper as
(b0, b1, ...,b7) whereas others set it out as (b7, b6,...,b0).
My own conclusion is that it does not really matter provided that (a) it is
clear which is being used, and (b) whichever is chosen is used consistently.
Unfortunately some specifications did not meet either of these criteria.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: A5/1 attack implementation?
Date: 12 Oct 2000 07:56:02 GMT
According to David A Molnar <[EMAIL PROTECTED]>:
> If I remember correctly, the paper notes that the authors implemented it
> on a desktop PC for testing purposes.
Actually, the paper states that they implemented the thing but did only
some sampling on the pre-computation (2^48 operations is actually quite
some job), so the correct answer is that there is no complete publicly
announced implementation of the attack, but there is one implementation
that only requires a few weeks/months of computation to become fully
operational.
--Thomas Pornin
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Thu, 12 Oct 2000 08:06:09 GMT
Anonymous wrote:
> Thanks in advance. I hope no one thinks I'm a troll.
Why on Earth not?
------------------------------
From: "Rob Marston" <[EMAIL PROTECTED]>
Subject: Re: What is meant by non-Linear...
Date: Wed, 11 Oct 2000 17:31:29 +0100
So to put it in a nutshell, if I had two S-Box's {the first is an Xor
and the Second is an And} then...
SBox Out Out
In Xor And
00 0 0
01 1 0
10 1 0
11 0 1
I could reverse the Xor S-Box by knowing the output bit and
either input bit, but I could not reverse the And operation?
Is that it?
Rob
------------------------------
From: "Rob Marston" <[EMAIL PROTECTED]>
Subject: Playfair Cipher Decoders...
Date: Wed, 11 Oct 2000 18:16:10 +0100
Can anybody recommend a good playfair Cipher solving program?
{dos /Windows only please :-) }
Rob
------------------------------
From: Andre van Straaten <[EMAIL PROTECTED]>
Subject: Re: Is it trivial for NSA to crack these ciphers?
Date: Thu, 12 Oct 2000 08:39:16 GMT
Anonymous <[EMAIL PROTECTED]> wrote:
> I'm not really interested in opinions of the relative strengths/weakness of various
>ciphers.
> I'm more interested to know what people think about NSA's ability to break messages
>encrypted with these ciphers.
You will get only rumours. A better understanding might have the chief of
a major spy agency. But I'm not sure if he will tell you.
> Which ciphers?
> How about any of the AES finalists?
> It seems to me that it wouldn't be out of the question for the FBI to get access to
>encryption breaking facilities at Ft. Meade if the believed there was significant
>risk to "national security".
> So what I'm trying to say is, if the FBI can break this stuff, it's pretty useless
>isn't it?
There are different tools and methods of cryptograhy as there are
different types of locks and alarm systems, or different types of weapons.
I keep my home and my car locked, knowing that the FBI or other
specialists might break in within 30 seconds or less.
> The Russians don't want the NSA reading their message traffic. What the hell do
>they use?
The Russians might have tanks, but you're not allowed to, don't have the
money, or don't have the know-how. So, you'll buy a hand-gun. Might be
helpful.
Not when a tank appears in front of your house. But is that likely?
Sorry about this question ;-)
> Thanks in advance. I hope no one thinks I'm a troll.
No, a simple but a good question. Hope you'll get lot of responses.
If you're a private person and you have only a few data to hide, it's
feasible for you to use some simple methods where you can be confident
that they are unbreakable from a cryptoanalytic standpoint.
E.g., I can store a data file encrypting it with a One-Time-Pad in that
way that the ciphertext is a nice text from Shakespeare, the key is then
as large as the plaintext (and the ciphertext).
That's unbreakable for everybody because nobody can ever find out what
else a text of Shakespeare might contain.
But if you pass the key to others or if you have large amounts of text,
it becomes cumbersome to unfeasible.
And then, if "somebody" is really interested in my plaintext, some
nasty guys will just "ask" me or steal the key from my safe at home.
-- avs
Andre van Straaten
http://www.vanstraatensoft.com
______________________________________________
flames please to [EMAIL PROTECTED]
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: On block encryption processing with intermediate permutations
Date: Thu, 12 Oct 2000 08:52:35 GMT
Mok-Kong Shen wrote:
> If I prove a theorem and there is a weakness, say, it depends
> on the existence of a quantity p being prime and someone
> points out that in a degenerate case p can be 1 and hence
> the proof is invalid and I do a little modification such
> that this case can be avoided and a prime p still can be
> chosen, then my purpose of establishing the theorem is
> achieved, isn't it?
Only if that was the one and only flaw in the proof. In this
case your argument for security was nonsense. Both myself
and David Hopwood explained why the argument was wrong. The
attack was just one counterexample, and changing the scheme
in this way accomplishes nothing significant.
[...]
> > > > The FAQ says it well:
> > > >
> > > > If you don't have enough experience, then most likely
> > > > any experts who look at your system will be able to find
> > > > a flaw. If this happens, it's your responsibility to
> > > > consider the flaw and learn from it, rather than just
> > > > add one more layer of complication and come back for
> > > > another round.
> > >
> > > It suffices for me that you apparently don't have anything
> > > to say to what I wrote above now.
> >
> > The quote from the FAQ says something important.
>
> Something important but not what YOU say.
Can you really not see any connection between "consider the
flaw and learn from it" and my call for "a serious attempt
to understand the material"?
> The following
> in my signature is also important that you should read
> and remember.
> Was sich ueberhaupt sagen laesst, | Whatever can be said
> laesst sich klar sagen; | can be clearly said;
> und wovon man nicht reden kann, | and silence must be kept
> darueber muss man schweigen. | on what one cannot tell.
> |
> Ludwig Wittgenstein | (a translation)
> (1889 - 1951)
I was hoping that meant no more of those pretentiously styled
posts "On <some_topic>" that establish no significant result
on the topic.
--Bryan
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
