Cryptography-Digest Digest #495, Volume #13 Fri, 19 Jan 01 01:13:00 EST
Contents:
Re: AES sbox generating code. (Tom St Denis)
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: A Small Challnge ("rosi")
Re: Kooks (was: NSA and Linux Security) (Greggy)
Re: using AES finalists in series? (David Wagner)
Re: Differential Analysis (Benjamin Goldberg)
Re: Kooks (was: NSA and Linux Security) (Boris Kazak)
Re: using AES finalists in series? (David Wagner)
Re: SAC question (Splaat23)
Re: block algorithm on variable length without padding? (Splaat23)
Re: Dynamic Transposition Revisited (long) (John Savard)
Re: AES sbox generating code. (Benjamin Goldberg)
Re: Dynamic Transposition Revisited (long) ("John A. Malley")
Re: Help needed on plaintext cypher ("Thomas W. Barr")
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: AES sbox generating code.
Date: Fri, 19 Jan 2001 04:04:31 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> I've written some code to generate the sbox used in AES. I'm not
> certain if it's correct. Would someone check it for me?
Why not just do the code a brute force way that way you can be sure. Or just
use my affine.c/goodbox.c from my website (at geocities) to make it....
What I did is do a brute force search for the multiplicative inverse...
If you don't know what you are doing, DON'T DO IT! (or at least try to
understand it first).
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Thu, 18 Jan 2001 20:35:38 -0800
Wei Dai wrote:
> > Furthermore, it is not ZKP but "Statistical Limited-Knowledge".
> There's another paper by Wenbo Mao on the same page at the URL I gave
> earlier, which appears to present a ZKP for the same property. I
> haven't read it carefully though.
It looks to me like that is not zero-knowledge either.
"In this part of the analysis we measure the quantity of the
information leakage which may be observed from a proof transcript."
I just don't see what the point to any of this is. What is gained
by proving that the RSA key is a product of 2 primes instead of 3?
Or that the factors are roughly the same size? Of what possible
use could that info be to anyone?
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Fri, 19 Jan 2001 00:19:51 -0500
Benjamin Goldberg wrote in part in message
<[EMAIL PROTECTED]>...
>Mok-Kong Shen wrote:
>[snip]
>> (2) Are you sure that some practically useful D and E[i] and
>> E[j] with E[i]!=E[j] could satisfy your following requirement
>> for arbitrary m in a sufficiently large set?
>>
>> D(E[i](m)) = D(E[j](m)) = m
>
>Hmm, unless I'm mistaken, NTRU keys can fit this definition perfectly.
Ben,
You are not!
I do not think I take the RSA one. I do take this one. I will correct
myself and
say a bit more. No time today, though.
BTW, nothing else needs to change. The notion is still good. There still
is at
least one secure, working system based on the notion. But I will talk next
time.
Thank you very much, Ben.
--- (My Signature)
------------------------------
From: Greggy <[EMAIL PROTECTED]>
Subject: Re: Kooks (was: NSA and Linux Security)
Date: Fri, 19 Jan 2001 04:31:25 GMT
In article <948dah$h1u$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <[EMAIL PROTECTED]>,
> "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
>
> > > When you get done reading through that stuff, if you are
interested,
> > > do a search on the "missing thirteenth amendment"
> >
> > The claim that it was ratified by a 13th state relies entirely on
> > the Virginia legislature's Act No. 280: "... there shall be
published
> > an edition of the Laws of this Commonwealth in which shall be
> > contained ..." and the subsequent publication of the Virginia
> > Civil Code containing the proposed 13th Amendment among other
> > US and Virginia laws. At that time (1819) there were 21 states,
> > so even if Virginia had thereby ratified the amendment (which
> > is debatable, to say the least), it would have still failed to
> > gain the required 3/4 approval (16 states, not 13).
>
> A through article at www.thirdamendment.com/missing.html explains this
> point in greater detail (if it isn't what you're relying on already).
>
> It also talks a bit about the amendment process in general, such as
that
> publishing a book that includes an amendment can't be construed as a
> ratification of an amendment. And notes that the same kooks who claim
> the 16th amendment wasn't ratified because of changes in spelling,
etc.
> conveniently ignore the same issues for the "missing 13th amendment."
>
> But not that one can expect much rational thought from these kooks.
They
> also claim that the "missing 13th amendment" gives them the right to
> murder cops (because being a police officer is a "title of nobility,"
> doncha know).
It is interesting - very interesting - that you refer to me as "one of
those kooks" using that phrase or term as many times as you can in your
post.
It is also interesting that NO ONE during the period in question in the
position of legislature or judicial screamed or even complained about
the Virginian process to publish the 13th amendment in its 1819
publication, and in fact other states as well when they chose to do the
same. Their actions show absolutely conclusively that they knew it was
properly ratified. You cannot explain the deafening silence when those
critical decisions were being made other than they knew it was correct
to publish the amendment because it was law. In fact, you have to say
they were all kooks for including it.
So we can see who the real kook is.
--
13th amendment to the US Constitution:
If any citizen of the United States shall accept, claim, receive,
or retain any title of nobility or honour, or shall, without the
consent of Congress, accept and retain any present, pension, office,
or emolument of any kind whatever, from any emperor, king, prince,
or foreign power, such person shall cease to be a citizen of the
United States, and shall be incapable of holding any office of
trust or profit under them, or either of them.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: using AES finalists in series?
Date: 19 Jan 2001 04:40:30 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Bryan Olson wrote:
>Where AES shines is the real world, where crypto has to be
>integrated into the systems people actually use, and where the
>budget for encryption is not set by the cryptographers. For
>every system that has one competently deployed cipher, there's
>a cryptographer who fought hard.
Well said.
Bottom line: It doesn't matter how secure your cipher is if it is not used.
Given that the usual reason/excuse not to use crypto is performance,
it behooves us not to sacrifice speed unnecessarily.
Anyway, in practice the way you break real systems won't be by breaking
AES. Spending a lot of effort thinking about tripling AES just isn't
worth your time. The difference between AES and 3AES is so far down in
the noise for most real systems...
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Fri, 19 Jan 2001 04:42:24 GMT
Tom. Your sboxgen will not generate the AES sbox. Or at least, it
might, but not in the lifetime of the universe.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Kooks (was: NSA and Linux Security)
Date: Fri, 19 Jan 2001 04:43:16 GMT
Greggy wrote:
>
> ******************
> --
> 13th amendment to the US Constitution:
> If any citizen of the United States shall accept, claim, receive,
> or retain any title of nobility or honour, or shall, without the
> consent of Congress, accept and retain any present, pension, office,
> or emolument of any kind whatever, from any emperor, king, prince,
> or foreign power, such person shall cease to be a citizen of the
> United States, and shall be incapable of holding any office of
> trust or profit under them, or either of them.
>
> Sent via Deja.com
> http://www.deja.com/
====================================
You better tell this to all Nobel Prize laureates (and and strip them
all out of American citizenship).
Usually I end my messages with the words "Best wishes".
Sorry, in this cannibalistic case I just cannot do it.
BNK
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: using AES finalists in series?
Date: 19 Jan 2001 04:43:51 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Benjamin Goldberg wrote:
>Terry Ritter wrote:
>[snip]
>> If one could make a cipher weaker simply by adding another ciphering
>> layer, that would be a way to attack the cipher. Yet we don't see
>> such attacks. Why?
>
>Sliding attack?
No, I think Terry Ritter has got it exactly right.
Sliding attacks don't work when you use independent keys, and if
you're thinking about chaining ciphers, you've got to use independent
ciphers, or else all bets are off.
One can formally prove that chaining is at least as secure as the
underlying cipher (as long as you use independent keys) -- it's an
easy exercise for a theory of crypto class -- and the proof is just
a formalization of Terry Ritter's observation.
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: SAC question
Date: Fri, 19 Jan 2001 04:47:42 GMT
Is there much advantage to having sboxes that are two-way SAC? Your 3x3
box below is only one-way SAC, which I assume would be sufficient since
that is the most important way, but there are strong biases in the
inverse.
In article <948d8s$gqb$[EMAIL PROTECTED]>,
Tom St Denis <[EMAIL PROTECTED]> wrote:
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > Tom St Denis wrote:
> > [snip]
> > > Given a function F, of size 2^n.
> > >
> > > Table A[n][n] initialized to zero
> > >
> > > for x = 0 to n
> > > for y = 0 to n
> > > for z = 0 to 2^n
> > > if flipping bit 'x' of 'z' causes bit 'y' of the output to flip
> > > (i.e (F(z) ^ F(z^(1<<x))) & (1 << y))
> > > add one to A[x][y]
> > > else
> > > sub one from A[x][y]
> > > next z
> > > next y
> > > next x
> > >
> > > If all the entries of A[][] are zero it's SAC.
> >
> > I would like you to present me with any 2x2 table which is SAC.
>
> Righto, but I did find a 3x3 sbox with SAC... So they don't exist for
2x2
> doesn't mean they don't exist for larger ones.
>
> sbox: { 7, 6, 3, 5, 4, 0, 2, 1 }
>
> Tom
>
> Sent via Deja.com
> http://www.deja.com/
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Splaat23 <[EMAIL PROTECTED]>
Subject: Re: block algorithm on variable length without padding?
Date: Fri, 19 Jan 2001 04:52:35 GMT
Maybe I'm missing something, but if the main point of this is to
encrypt a message without expanding it, why not pick any of the secure
block cipher modes that generate a keystream like a stream cipher.
That's basically what we want here anyway if space is that important.
Use the block cipher in a stream mode, and cut the keystream to message
length and XOR. Done!
In article <948d91$7ji$[EMAIL PROTECTED]>,
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote:
>
> N. Weicher <[EMAIL PROTECTED]> wrote in message
> news:rUJ96.5688$[EMAIL PROTECTED]...
> > I'm not sure I follow you. Let's say that you have N blocks, but
the Nth
> > block contains less than 8 bytes (for convenience we'll assume N >
1 so we
> > know we have at least one full block).
> >
> > Are you saying that the final block is computed as follows? I.e.,
the
> > partial final block is XORed with the next to last encrypted block?
> >
> > C(N) = P(N) ^ C(N-1)
> >
> > In this case, all you need to do to recover the final partial block
is to
> > XOR it with the encrypted next-to-last block. You don't even need
to know
> > the key.
> That doesn't work: You don't need to know the key to get the final
partial
> block, and *neither does the attacker*. Doing:
>
> C(N) = P(N) ^ E(C(N-1))
>
> would work, but that's not what's Don's suggesting.
>
> >
> > If this is not what you mean, how are you encrypting the final
partial
> > block?
> Simple: Then, you first encrypt the first N-1 blocks as normal.
Then, you
> append the final partial block to the ciphertext, and then encrypt
the last
> 8 bytes (i.e. full block) of the result to form the message.
>
> To decrypt, the receiver decrypts the last 8 bytes of the message,
and then
> decrypts the first N-1 blocks as normal. This reconstructs the
original
> message.
>
> --
> poncho
>
>
Sent via Deja.com
http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 19 Jan 2001 05:21:13 GMT
On Fri, 19 Jan 2001 03:41:40 GMT, Benjamin Goldberg
<[EMAIL PROTECTED]> wrote, in part:
>You seem to be ignoring that before shuffling, the data is accumulated
>into bit-balanced blocks. Did you read the whole paper?
I admit that I only skimmed through it. I saw the word 'bit-balanced',
but didn't look closely.
Upon looking again, I see that he indeed explicitly mentioned this
point. However, I note that details of bit-balancing were not given.
If the data is *not* pre-processed or compressed or whatever, and if
the point at which a block is cut off depends on what bits are in the
block (and the extent of the need for balancing) then that has to be
indicated somehow, and the indications need to be encrypted...
this could get quite messy.
Of course, a *simple* way of dealing with this problem would be to
code 6 bits of binary input to an 8-bit byte in a 4 of 8 code, using
64 of the 70 possible values. This would be a brute-force approach,
but it would mean that one would not have a data-dependent concern
with the block lengths. They could be uniform, or chosen randomly.
I suppose even with a substitution phase, if one ensures bit balance,
the transposition phase is made maximally strong; but _then_ one has a
redundancy problem (since after transposition, any simplistic scheme
of ensuring bit balance wouldn't be preserved - i.e. after a bit
transpose of bytes in a 4 of 8 code, each byte of the result would not
necessarily have exactly four 1 bits).
Of course, data already _encrypted_ by a substitution phase could be
assumed or hoped to have good enough bit balance, or failing that the
substitution could be strong enough to ensure security. (If the
substitution is on short blocks, then the key for the substitution
must vary with each short block, else a plaintext consisting of
identical short blocks could send a signal through the
transposition...)
Basically, the problem is that bit-balanced binary data and raw
arbitrary binary data aren't a good fit to each other.
Six bits of arbitrary binary data -> 8 bits of 4 of 8 coded data -> 8
bits of binary data having an overall bit balance
means that the 8 bits of finally-encrypted data can't be compressed
all that much.
Of course, the initial means of achieving bit-balance needn't be as
inefficient as a 4 of 8 code, but it still *won't* be fully optimal
over the entire transposition block length. Whatever means of
obtaining bit-balance is used, it will need a smaller "window" than a
whole transposition block to be reasonably efficient.
This expansion of the data will, I fear, like the autokey nature
(making for poor error-recovery properties) of Dynamic Substitution,
condemn Dynamic Transposition in the specific form described here to
marginality. The market does not want to hear of encryption methods
that are awkwards - that can't be used, for example, to encrypt a
sector of a disk and fit the encrypted result in a sector of a disk.
Combining substitution and transposition - and using a Feistel-like
structure to make the transposition key for one half of a block depend
on the contents of the other half (thus obtaining the variability Mr.
Ritter rightly notes as essential to avoid multiple anagramming) - is
capable of producing a much more well-behaved and "conventional"
cipher.
This is not to say, however, that the concepts presented here are not
useful. Terry Ritter has shown how one _could_, even at the cost of
inconveniences people aren't usually willing to bear, make a secure
cipher based on transposition alone. This is of theoretical
significance, and that, all by itself, is genuinely valuable.
(It might also be noted that the requirement that each transposition
step must uniformly be capable of producing all N! permutations of
bits is likely to make the transposition steps computationally
inefficient, so I think that this is another unfashionable aspect of
the specific proposal given. Although in this case, unfashionable does
not mean unsound: that is a desirable ideal.)
The fact that bit balancing is not going to produce, by any reasonable
algorithm, all N!/(N/2)!^2 possible bit-balanced blocks as input to
the transposition, my earlier objection to this scheme, also impinges
on the value of this...
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: AES sbox generating code.
Date: Fri, 19 Jan 2001 05:34:27 GMT
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > I've written some code to generate the sbox used in AES. I'm not
> > certain if it's correct. Would someone check it for me?
>
> Why not just do the code a brute force way that way you can be sure.
> Or just use my affine.c/goodbox.c from my website (at geocities) to
> make it....
Is your affine() in affine.c the *same* affine transform as the one used
by AES? Your thing takes up 8 lines. Anyway, I'm fairly certain that I
at least got that part right:
j = i ? pow[255 - log[i]] : 0;
k = ((j >> 7) | (j << 1)) ^ ((j >> 6) | (j << 2));
j ^= 0x63 ^ k ^ ((k >> 6) | (k << 2));
Especially since it is copied from one of the reference implementations.
Can the functions in goodbox.c be used to make the function log3(x) mod
2 mod p? Maybe, but not easily.
> What I did is do a brute force search for the multiplicative
> inverse...
How do multiplicative inverses relate to powers and logarithms of 3?
> If you don't know what you are doing, DON'T DO IT! (or at least try to
> understand it first).
If *you* don't know *what* I'm doing (and it seems you don't), then
don't try to tell me *how* to do it or not do it.
Anyway, since seeing your Trollish posting in response to my question, I
did a search for AES implementations. Take a good, hard, look at the
gen_tabs() function in the following:
http://fp.gladman.plus.com/cryptography_technology/rijndael/aes.c
, and then tell me that my code is wrong. Dare ya!
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Thu, 18 Jan 2001 21:46:47 -0800
Terry Ritter wrote:
[snip]
>
> One of the needed components which has not been described
> is the bit-balancing process.
>
> Bit-Balanced Blocks
>
> Some of the analytic and strength advantages of Dynamic
> Transposition depend upon having the same number of 1's
> and 0's in each block, which is called "bit-balance."
> Exact bit-balance can be achieved by accumulating data to
> a block byte-by-byte, only as long as the block can be
> balanced by adding appropriate bits at the end. Then the
> block is ciphered, and another block filled.
>
> We will always add at least one byte of "balance data,"
> at the end of a block, and only the first balance byte,
> immediately after the data, will contain both 1's and 0's.
> We can thus transparently remove the balance data by
> stepping from the end of the block, past the first byte
> containing both 1's and 0's.
I had a few immediate hunches about cryptanalysis of dynamic
transposition but realized they may spring from misunderstanding of the
algorithm.
May I paraphrase the description of block balancing to make sure I
understand the mechanism as envisioned? And please, correct me if I got
this wrong.
Given plaintext P,
1) divvy P into bytes as P[1], P[2], P[3] ... P[n],
2) build up (one at a time) blocks of size k bytes, B[1], B[2], B[3]
... B[m] where m < n, and sequential plaintext bytes are assigned to a
given block B[i] where B[i] is the concatenation of a few plaintext
bytes, followed by a special byte that has 0s and 1s in it, followed by
bytes of all zeros or all ones - like
P[1] | P[2] | ... | P[L] | a block of 1s and 0s | 00000000 | 11111111 |
... 00000000 = B[i]
or
P[1] | P[2] | ... | P[L] | a block of 1s and 0s | "0" | "255" | ...
"0" = B[i]
Is this an accurate description of the proposed bit balancing?
I'm curious about fixed bit patterns or expected bit patterns (if any)
that end up in the appended plaintext, for they may serve as the chink
in the armor for cryptanalysis.
For example, consider
11111000 | 11111000 |
as plaintext, which is then followed by a "signal byte"
11111000 | 11111000 | 00110011 |
to "balance out" the 1s and 0s in the first two bytes of plaintext, a
then followed by two bytes of all 0s and all 1s to round off the block
as
11111000 | 11111000 | 00101010 | 00000000 | 11111111
or, also acceptable,
11111000 | 11111000 | 00101010 | 11111111 | 00000000
Can that "signal" byte take on only certain values when it "balances"
the preceding bytes, and can the bytes of "0" and "255" value following
occur in any order, or is it a fixed order?
Uh-oh.
I just realized I must have this wrong. I came up with an example that
won't balance the way I described above -
10000000 | 00000000 |
there is no value I can plug into the "signal" byte that's a mixture of
1s and 0s, to follow these, that gets followed by all 0 and all 1s
bytes, that balance the resulting block.
10000000 | 00000000 | XXXXXXXX | 00000000 | 11111111
Please help, how does the bit-balancing work?
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "Thomas W. Barr" <[EMAIL PROTECTED]>
Crossposted-To: rec.puzzles
Subject: Re: Help needed on plaintext cypher
Date: Fri, 19 Jan 2001 05:58:55 GMT
You might have more luck on a puzzle NG.
We usually deal w| crypto (RSA, DES, PGP, etc.) Don't take this as we are
too good for this stuff, it's just I'm not very good at these kind o'
things. (I wish I was, though:-( )
Good luck,
Thomas W. Barr
[EMAIL PROTECTED]
"Keith" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I need help to decipher a seasonal message in a devious
> christmas quiz. I'm no cryptographer, so I haven't a chance with this. All
> assistance welcomed. Help will be acknowledged in our answer.
>
> Thanks, Keith
>
> The quiz question reads:
>
> An easy cipher this year, though the following plaintext is not easy at
all.
> THE HOLIDAY SEASON IS KEPT FOR THE PIANISTS, BUT THEY PRAY THAT ANY
MUSICAL
> PIECE (HARMONIOUS OR OTHERWISE) IS LESS THAN AN HOUR LONG. THE TIME MUSIC
> PLEASANTLY OCCUPIES IS TIME THAT PEOPLE AND ANGELS CAN RELAX.
>
>
------------------------------
** 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
******************************
