Cryptography-Digest Digest #324, Volume #14 Wed, 9 May 01 23:13:01 EDT
Contents:
Re: Random and not random (Bryan Olson)
Re: research on polymorphic crypto/Best Possible Privacy? (Mark Wooding)
Re: Random and not random (Matthew Skala)
Re: Random and not random (Bryan Olson)
Re: Crypto web-page ("Scott Fluhrer")
Re: Crypto web-page ("Tom St Denis")
Security with provable strength. (Benjamin Goldberg)
Re: Crypto web-page (John Savard)
Re: 3x4 grid of triangular numbers (Benjamin Goldberg)
Re: Weird Rijndael test vectors wanted (Mark Wooding)
Re: Security with provable strength. (Paul Rubin)
Re: mathematical definition of phi (Jim Steuert)
Re: Bleaming strock cipher ("Paul Pires")
----------------------------------------------------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Wed, 09 May 2001 17:44:26 -0700
Mok-Kong Shen wrote:
>
> Bryan Olson wrote:
> >
> > Mok-Kong Shen wrote:
> >
> > > To more thoroughly clear the matter up, let's consider
> > > a hypothetical yet concrete scenario. Suppose I am the
> > > cipher clerk and you are my boss, the chief of the
> > > encryption department.
> >
> > You would be so fired.
> >
> > > I come to you and tell you that
> > > I have 3 OTP segments and 3 messages to encrypt and ask
> > > you whether there is any difference with the choice of
> > > the 6 possible permutations for sending the messages,
> > > i.e. whether the opponent could have a better chance
> > > to crack in the one case than in the other. What would
> > > be your answer?
> >
> > It would be the same correct answer that multiple people
> > have already given you many times: Just be sure the
> > choice of permutation is independent of the content of
> > the segments. See my previous posts, or Matthew Skala's
> > posts or James Felling's posts.
>
> But this is a Yes/No question, isn't it?
As I've already written more than once in this thread, many
of your questions do not have answers of the form you expect.
This is one of them, and Matthew Skala explained why long
ago. See his posts from last Thursday on, and the follow-ups.
> In all business transactions [...]
Your view is wrong and restating it in yet another form will
not help.
> Why should crypt be any different in
> that 'general' behaviour?
For exactly the reasons already shown by several people many
times.
> Note that, if a dependency
> on the content of the OTP segments could result in
> any difference, that means directly I could determine
> one permutation out of the 6 that the opponent has the
> least chance of success and consequently I should have
> chosen that one, instead of making a random choice (your
> independent choice). Is that right?
It is wrong. We assume the method, but not the key, is
known to the attacker. See Shannon's paper or the FAQ.
--Bryan
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: research on polymorphic crypto/Best Possible Privacy?
Date: 9 May 2001 19:14:08 GMT
I'm not entirely convinced that Mark G Wolf was serious when he posted
the article I'm following up to. But I'll take the bait anyway.
Mark G Wolf <[EMAIL PROTECTED]> wrote:
> Are you from the propaganda ministry?
Not so as I noticed. Of course, maybe they manipulated my mind so that
I work for them anyway.
> Or just plain stupid?
Could be. Not sharing other people's prejudices is a symptom of
stupidity, after all.
> This is the future of cryptography. Done right, it's unbreakable.
This is all down to what you mean by `done right'. With a suitable, and
plausible, definition, any cipher `done right' is unbreakable. I
assume that you didn't mean to write such a tautology, so you'd better
explain what you actually meant.
What `polymorphic cryptography' actually seems to do is make
quantitative analysis hard. This is a real shame for poeple like me,
who want good hard quantitative analysis of ciphers before we use them.
I'd rather use a simple cipher, like Rijndael, or Blowfish, where I can
see what each individual bit does and why.
Cipher design is a mixture of mathematics and mess (I can't remember who
said this first; might have been Bruce Schneier). My leaning is
certainly towards the `mathematics' side. The more mess you have, the
more you have to wave your hands to convince someone else that your
cipher is good. Ideally, you'd need no handwaving at all, so you'd have
all maths and no mess.
This `polymorphic cryptography' seems to be almost all mess: lots of
handwaving, lots of big numbers and crossed fingers; nothing convincing,
no hard facts. All of the information about the system I could find
seemed to be handwaving with no particular justification. A reputable
cryptographer, I assert, wouldn't behave like this; hence I label
polymorphic cryptography, at least as perpetrated by this organization,
`snake-oil'.
> It's from the Germans, that should make it obvious that it's good.
This would be `proof by nation of origin'. Is this why we chose
Rijndael to be AES? Well, I know of research explaining why Belgians
are the best cryptographers, so maybe this was taken into consideration
[MR98], but I'd rather choose my ciphers based on their merits.
References
[MR98] Keith M. Martin and Vincent Rijndael, `The First Official
Crypto-World Rankings', Journal of Craptology Volume 0 No. 0,
1998 (Lars Knudsen, ed.)
-- [mdw]
------------------------------
From: [EMAIL PROTECTED] (Matthew Skala)
Subject: Re: Random and not random
Date: 9 May 2001 17:50:34 -0700
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>Matthew Skala wrote:
>> Want to play the game? If not, why not, and how is it meaningfully
>> different from your OTP scenario?
>
>My answer sounds unbelievable but is true. Unfortunately
>(maybe fortunately), I have never played any card games in
>my life.
OK, I'll reformulate it as an integer game.
I have a machine that generates random integers and seals them in
envelopes without telling me or anyone else what integers it
generates. You, I, and anyone else can inspect this machine's workings
and we all agree that it does its job correctly and fairly; presented with
a sealed envelope from the machine, we all agree that none of us know what
integer is inside.
So I use the machine to generate two integers. Here are the two
envelopes, one on the left and one on the right. Suppose I pick the one
on the left for myself and give you the one on the right, then we open our
envelopes and whoever has the greater integer wins the game. That seems
to be a fair game. Suppose I pick the one on the right for myself and
give you the one on the left, then we open our envelopes and whoever has
the greatest integer wins the game. Suppose I flip a coin or make
some other random decision to choose which envelope I take and which
one I give to you, before we open our envelopes and compare integers.
All those games seem fair. It seems like it shouldn't matter which
envelope I take for myself and which one I give to you. I should be FREE
to CHOOSE a PERMUTATION of envelopes and players.
So, now I open both envelopes and look at the integers. Then I choose one
for myself and give the other to you, and whoever has the greatest one
wins. Is that game fair? Suppose the on one the right was greatest, and
I chose that one, and I won. Was that fair? It would have been fair if I
made that choice before opening the envelope, so that was a fair choice,
so it should still have been a fair choice after I looked at the numbers,
right?
Even if you have some objection to actually playing games of chance, I
would hope that you can still comment on whether that hypothetical game
would or would not be fair.
--
Matthew Skala
[EMAIL PROTECTED] "I fish stranger things than you
http://www.islandnet.com/~mskala/ out of my granola every morning."
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Random and not random
Date: Wed, 09 May 2001 18:04:53 -0700
Mok-Kong Shen wrote:
>
> James Felling wrote:
> >
> [snip]
> > Ok. Let me try and formalize it.
> [snip]
>
> I suppose that, in order to avoid eventual unnecessary
> debates, it is best that I settle first an apparent
> misunderstanding between Bryan Olson and me.
My writing in this thread has repeatedly, from the beginning,
recommended you study James Felling's posts. Don't you dare
use me to justify ignoring another of his clear and carefully
written arguments. To settle your misunderstanding and avoid
unnecessary debate, start studying the answers that people have
worked so hard to put before you.
--Bryan
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Crypto web-page
Date: Wed, 9 May 2001 18:17:30 -0700
<[EMAIL PROTECTED]> wrote in message
news:9dc9rb$jdd$[EMAIL PROTECTED]...
> Hi all,
>
> I've added a cryptography page to my web-site:
>
> http://www.wizardsworks.org/robin/crypto.html
>
Question: why is "Use of any block-cipher algorithmn[sic]" a "Common
Cryptographic Mistake"? Please include references.
--
poncho
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Crypto web-page
Date: Thu, 10 May 2001 01:33:12 GMT
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:9dcqtg$9s6$[EMAIL PROTECTED]...
>
> <[EMAIL PROTECTED]> wrote in message
> news:9dc9rb$jdd$[EMAIL PROTECTED]...
> > Hi all,
> >
> > I've added a cryptography page to my web-site:
> >
> > http://www.wizardsworks.org/robin/crypto.html
> >
> Question: why is "Use of any block-cipher algorithmn[sic]" a "Common
> Cryptographic Mistake"? Please include references.
The website is complete BS. I wouldn't bother with it.
Obviously the person who made it is either a crank or doesn't understand a
thing about modern crypto.
I.e "Failure to implement protection against "known plain-text" attacks."
which is impossible except for physical protection.
and
"In the context of a public-key cryptography system: Thinking it's safe to
send a public-key across an insecure network or communications medium, such
as the internet. Since we all know that sending a public-key across an
insecure network means someone can intercept it "en route" and replace it
with his/her own."
Which is only half true. Using a web of trust it's possible todo this
correctly.
or also
"Widespread use of the RSA public-key algorithm, when there are superior
alternatives. "
Which is stupid since RSA has yet to be broken and RSA is far simpler then
"surperior" algorithms
Tom
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Security with provable strength.
Date: Wed, 09 May 2001 22:30:22 -0400
I recall reading of this scheme in AC, but I don't recall the name of it
offhand.
The two parties wanting to communicate securely share an N-bit key.
They want to securely transmit from one to the other over an open line
an M-bit message which they *know* will take 2^N work for the opponent
to break (even against chosen plaintext/ciphertext attacks).
To do this, the sender sends to the reciever N truly random strings,
each M bits long. Then, he XORs the plaintext together certain of those
strings, as determined by the bits of the key, to create the plaintext.
I have two questions: one, what's its name (I'm sure someone remembers,
even if I don't), and two, how does this scheme compare to Rabin's
"unbreakable" encryption scheme -- assume that the random strings can be
gotten from the same sort of random source that Rabin's scheme uses.
--
Shift to the left, shift to the right, mask in, mask out, BYTE, BYTE,
BYTE !!!
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Crypto web-page
Date: Thu, 10 May 2001 02:29:40 GMT
On Wed, 9 May 2001 18:17:30 -0700, "Scott Fluhrer"
<[EMAIL PROTECTED]> wrote, in part:
>Question: why is "Use of any block-cipher algorithmn[sic]" a "Common
>Cryptographic Mistake"? Please include references.
Maybe what he meant was use of ECB mode (instead of CBC mode, for
example) is a "common cryptographic mistake".
I know I'm being rather charitable, but it _is_ possible.
John Savard
http://home.ecn.ab.ca/~jsavard/
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles,alt.math.recreational,sci.math
Subject: Re: 3x4 grid of triangular numbers
Date: Wed, 09 May 2001 22:34:44 -0400
Fred W. Helenius wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
>
> >Could someone direct me to Gau�'s proof that any number can be
> >decomposed into the sum of 3 triangular numbers?
>
> Section V of his _Disquisitiones Arithmeticae_. The theorem
> is stated and proved in article 293, but the proof depends
> upon "the preceding theory"; that is, the theory of quadratic
> forms that he develops in the preceding 200+ pages.
Uck. Is there any *simple* proof for this? And, how hard is it to
decompose an arbitrary large number?
--
Shift to the left, shift to the right, mask in, mask out, BYTE, BYTE,
BYTE !!!
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Weird Rijndael test vectors wanted
Date: 10 May 2001 02:44:38 GMT
Simon Josefsson <[EMAIL PROTECTED]> wrote:
> Do you get these values? I do, but I just added Nk={5,7} support to
> my implementation so it's not verified to be correct. (Nb=4)
>
> KEY=0000000000000000000000000000000000000000
> PT=00000000000000000000000000000000
> CT=32CB23EE8DEBD0D4E0983EE4D3318A5F
>
> KEY=00000000000000000000000000000000000000000000000000000000
> PT=00000000000000000000000000000000
> CT=BE47C9BF5D104A8EC32A13C94596237C
No. I get neither.
I've managed to get the reference implementation and mine to agree, but
it took a lot of hard work and headscratching. (There are lots of
switch statements to work out numbers of rounds and whatever, and the
key schedule is just wrong for Nk = 7.) I'm still not convinced I'm
right, and would like independent confirmation.
I now get these test vectors:
KEY=0000000000000000000000000000000000000000
PT=00000000000000000000000000000000
CT=94B434F8F57B9780F0EFF1A9EC4C112C
KEY=0000000000000000000000000000000000000000000000000000000
PT=00000000000000000000000000000000
CT=73F8DFF62A36F3EBF31D6F73A56FF279
-- [mdw]
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Security with provable strength.
Date: 09 May 2001 19:49:16 -0700
It was attributed in AC2 to Udi(sp?) Maurer, but it's completely
insecure and there has to be some kind of mistake involved.
Think linear algebra.
------------------------------
From: Jim Steuert <[EMAIL PROTECTED]>
Subject: Re: mathematical definition of phi
Date: Wed, 09 May 2001 23:01:02 -0400
Reply-To: Jim, Steuert
There is an excellent port of the gcc compiler to the ti89 (and ti92p)
(10Mhz 68000)
called tigcc, and excellent ports of various libraries. The ti89 even has
some rsa
functions. I've actually used tigcc for a single 4000+ line c program.
And also an excellent emulator for the pc called vti.exe. I don't know
of any port of a bignum type library. On this version of gcc, int means
short, so
be sure to use "long int" for 32-bit ints. The ti89 and ti92p (I have
both) are
great, albeit a bit slow compared to a 150 Mhz mips or 206Mhz strongarm
pocketpc.
(there is a free dev kit from Microsoft for the pocketpc also, which I've
used)
Dopefish wrote:
> is there some sort of mathematical expression that i could use to find
> phi(n) on my TI-89 calculator?
>
> fish
>
> --
> ------BEGIN SIGNATURE------
> A.K.A "Dopefish" or "fish" for short on Usenet.
>
> Microsoft? Is that some kind of toilet paper?
>
> "Rockin' the town like a moldy crouton!"
> - Beck (Soul Suckin' Jerk - Reject)
>
> "Help me, I broke apart my insides. Help me,
> I've got no soul to sell. Help me, the only thing
> that works for me, help me get away from
> myself."
> - Nine Inch Nails (Closer)
>
> -----BEGIN GEEK CODE BLOCK-----
> Version: 3.12
> GO dpu s++:++ a---- C++++ U--->UL
> P L+ E? W++ N+++ o+ K--- w+>w+++++
> O--- M-- V? PS+++ PE Y-- PGP t 5--
> X+ R tv b+ DI D+ G-- e- h! r z
> ------END GEEK CODE BLOCK------
> (www.geekcode.com)
>
> ------END SIGNATURE------
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Bleaming strock cipher
Date: Wed, 9 May 2001 20:03:00 -0700
Scott Fluhrer <[EMAIL PROTECTED]> wrote in message
news:9dajmv$eka$[EMAIL PROTECTED]...
>
> Paul Pires <[EMAIL PROTECTED]> wrote in message
> news:hKXJ6.8753$[EMAIL PROTECTED]...
> > The following is a cipher concept I have been working on.
> > This material is very similar to the last concept I posted, the
> > one that Scott Fluhrer and Brian Olson euthanized on contact.
> > The idea is a stream cipher that processes it's output in large
> > blocks. The goal is to have a cipher that is:
> >
> > 1, relatively simple.
> > 2, very fast.
> > 3, internally obscure, one that does not reveal it's internal state
> > so easily for a chosen or known plaintext attack and one that
> > is safe against bit-flipping.
> >
> > This cipher is simple (in code) and runs at 8.3 clocks per byte
> > Note: No file I/O.
> >
> > The basic idea is to use two different sets of internal tables.
> > One table, "A", is dynamically changing and its values are used
> > only as location arguments for retriveing and storing values
> > from the plaintext, ciphertext and the other table, "B". Both
> > tables, A&B are split in two and handled seperately as A0,A1, B0,B1.
> > Each cycle, the operations performed on these table halves
> > alternate. Pointers are assigned to these table halves (A_old, A_new
> > & B_old, B_new) and to alternate, the pointers are just re-assigned
> > (swapped) for each cycle. So, here are the pieces:
> >
> > "A0" and "A1" together comprise table "A" and are 64 element tables, each
> containing the
> > values 0-63 initialized in a key dependent way. (unsigned char[75])
> > Note: 11 bits from the front of the array are duplicated at the end.
> >
> > "B0" and "B1" together comprise table "B" and are each 64 element tables.
> Each element is 32
> > bits wide and are also initialized in a key dependent way. (unsigned
> int[64]) .
> >
> > "A_new" and "A_old" are pointers that can be set and reset to the A
> tables. (unsigned char*)
> > "A_new_32" is a 32 bit wide pointer which is always set to the new "A"
> address. (unsigned int*)
> > "B_new" and "B_old" are pointers that can be set and reset to the B
> tables. (unsigned int*)
> >
> > After every text block is processed (cycle) the pointers are re-set so
> that what
> > once was an old table becomes the new table and its values are then
> updated,
> > First "B" then "A". Cyphertext and plaintext are handled as 32-bit units
> and
> > are processed as blocks of the same length as a "B" table (64 elements).
> >
> > To process a block:
> >
> > Encrypt:
> > for (i=0, i<64, i++)
> > {
> > C[A_old[A_new[i]]] = B_old[A_new[i]] ^ B_new[A_old[i]] ^ P[i];
> > }
> >
> > (Decrypt would be:
> > P[i] = B_old[A_new[i]] ^ B_new[A_old[i]] ^ C[A_old[A_new[i]]] ;)
> >
> > Reset B pointers alternately. (odd is just the last bit of the cycle
> counter "x")
> >
> > B_new = (odd) ? (unsigned int*) &B0 : (unsigned int*) &B1;
> > B_old = (odd) ? (unsigned int*) &B1 : (unsigned int*) &B0;
> >
> > Update the Old (now named new) State B table. B1 in the case where the
> > cycle count "x" is even:
> >
> > unsigned int wrapper = x ^ (B_new[0]<<27);
> > for (i=0, j = 1, k = 63; i<63; i++, j++, k--)
> > {
> > B_new[i] = (B_new[i]>>5) ^ P[i] ^ C[A_new[k]] ^ (B_new[j]<<27);
> > }
> > B_new[63] = (B_new[63]>>5) ^ P[63] ^ C[A_new[0]] ^ wrapper;
> >
> > Now let's see if I've built another garage door and handed Pancho the
> > remote opener.
> Well, I hate to disappoint my fan club, so I'll start with this rather
> surprising observation: after the first block, the parity of a plaintext
> block and the parity of the corresponding ciphertext block is the same(!).
Well count me as a fan. It's a pleasure to watch you work and I do
appreciate that you could just as well point me to a link or advise
more schooling.
>
> Here's how it works: lets call the parity of a plaintext block, B_new array,
> B_old array and the ciphertext block P, B_new, B_old, C.
I suspect that you are using the term parity in a sense that I am not familiar
with. You have excized the re-arrangement due to the A tables so I guess
you are getting at an attribute of the lists as a whole, regardless of the element
arrangement. That part makes sense. Are you talking about the bit status of
each bit from some alignment being predominantly ones or zeros or some aspect
of the status of all the bits as a block lump?
>
> Case 1: Consider the case where B_new != B_old. Then, the encrypt process
> will set C := B_old ^ B_new ^ P = !P. Then, it swaps B_new and B_old, and
> then updates B_new := B_new ^ P ^ C = !B_new. Hence, it will handle the
> next block as case 2, as B_new = B_old.
Are you saying that the parity of B_new = B_old or that B_new is a duplicate of
B_old? I don't mean to sound dense here (that comes without trying) but it doesn't
seem to work that way (either way) in the code I have nor do I understand how
that could happen and not be detected by one test or another from Diehard. To tell
the truth, I haven't thought of these tests in terms of parity within a block before.
Diehard
wasn't specifically designed to look at generators that make output in 2048 bit blocks
so
I guess it could slip by. I guess I could do some of that thinking stuff and show why
this
is or is not the case but I'd really like to make sure that I understand you first. I
don't mind an
"exercize to be completed by the student" but I don't want to hare off in the wrong
direction.
>
> Case 2: Consider the case where B_new = B_old. Then, the encrypt process
> will set C := B_old ^ B_new ^ P = P. Then, it swaps B_new and B_old, and
> then updates B_new := B_new ^ P ^ C = B_new. Hence, in this case, C=P, and
> in addition, it preserves the condition B_new = B_old, and hence it will
> handle the next block as case 2.
Once again, I don't think I understand. The tests I run use all zeros for all plaintext
blocks and I assure you that the parity of the ciphertext blocks changes from block
to block whether looking at the block as a whole or at particular bit positions. I
must
not get what you're getting at. Can you help me out here? Is there some other meaning
for parity in an information theoretic sense? If the parity of the plaintext is always
zero
and the ciphertext is always the same, after 10 megs of ciphertext, the arithmetic mean
should be skewed. I just haven't seen it.
Got it! Yep, nothing mysterious just good old fasioned parity.
If I take out the xor of the block counter from the B update routine it does as
you say. With it in, the parity varies but not in an alternating fasion as one would
expect
but it is obviously not random by inspection. This is a Baaad descriminator and as
such is
not good but, a question from the student, can this observation be extended to a
substantial
attack?
Head slapper! It is so obvious now that you pointed it out. The repair is obvious too
but I'd much rather understand. Thanks.
I'm really surprised that none of the tests I ran caught this. I guess that says
something
about relying on tests. Maybe you just had your wheatees today.
Once again, I thanks for the insight.
Paul
>
> Hence, after the first block, the cipher will stay in case 2, and so will
> have P = C.
>
> --
> poncho
>
>
>
------------------------------
** 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
******************************
