Cryptography-Digest Digest #641, Volume #14 Mon, 18 Jun 01 17:13:00 EDT
Contents:
Re: Counter mode, the better way to do it? (Tim Tyler)
Re: Is ECB truly more secure than CBC? (David Wagner)
Re: SHA2 PRNG. ("Tom St Denis")
Re: survey (Mok-Kong Shen)
Q: XML-security (Mok-Kong Shen)
Re: survey (Benjamin Goldberg)
Re: survey (Mok-Kong Shen)
Re: Counter mode, the better way to do it? ("Tom St Denis")
Re: "computationally impossible" and cryptographic hashs (Benjamin Goldberg)
Re: XOR256 encryption/decryption method (Tim Tyler)
Sorry, I didn't know that was considered "spam" ([EMAIL PROTECTED])
Re: Single-cycle sbox question ("Henrick Hellström")
Re: decorrelated bitsliced cipher (Benjamin Goldberg)
Re: decorrelated bitsliced cipher ("Tom St Denis")
Re: Single-cycle sbox question ("Henrick Hellström")
Re: Single-cycle sbox question ("Tom St Denis")
----------------------------------------------------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Counter mode, the better way to do it?
Reply-To: [EMAIL PROTECTED]
Date: Mon, 18 Jun 2001 20:04:56 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote:
: "Julian Morrison" <[EMAIL PROTECTED]> wrote in message
:> Two approaches I've seen to doing CNT mode for Rijndael:
:> - use the raw count, say a 32 bit unsigned int in one quad of bytes and
:> the 12 remaining bytes as 0x00. [...]
:>
:> - feed the count through a scrambling function first, such as MD5.
:>
:> Which is safer and better?
: In a good cipher.....neither.
I presume that use of a hash would help eliminate the CTR mode proviso
that you change keys before you've transmitted sqrt(2^blocksize) blocks.
Note also that use of two cryptographic primitives might be seen as
slowing things down somewhat.
As Tom says, if your cypher's OK, there's no need to worry about the known
plaintext.
However if you *do* want to avoid it, you could do something like instead
of adding 1, add an odd constant with roughly the same number of 1 and 0
bits set in it, and rather than padding with 0s, duplicate the counter
across the block size. These are not expensive operations to perform -
in contrast to hashing - which has a large cost.
--
__________
|im |yler http://rockz.co.uk/ http://alife.co.uk/ http://atoms.org.uk/
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Is ECB truly more secure than CBC?
Date: Mon, 18 Jun 2001 20:14:02 +0000 (UTC)
Joseph Ashwood wrote:
>For encryption it's a bit more difficult, and will require feeding the
>oracle the same value a large number of times, at least enough to find a
>collision of values, call the original value A and the collicion A', call
>the value following A B, and the value following A' B'. If B==B' it was CBC.
With CBC, all bets are off once you get near the birthday bound
(once you encrypt enough blocks to find a collision, i.e., near
2^32 blocks with a 64-bit block cipher). The theorems only
promise security if the number of blocks encrypted is low enough
that no collision is likely. So, there is no contradiction.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: SHA2 PRNG.
Date: Mon, 18 Jun 2001 20:15:04 GMT
"Cristiano" <[EMAIL PROTECTED]> wrote in message
news:9glm23$739$[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> ha scritto:
> .> "Cristiano" <[EMAIL PROTECTED]> wrote in message
> .> news:9gknsa$rr0$[EMAIL PROTECTED]...
> .> > "Tom St Denis" wrote:
> .> > > "Cristiano" <[EMAIL PROTECTED]> wrote in message
> .> > > news:9gj15m$fan$[EMAIL PROTECTED]...
> .> > > > "Tom St Denis" <[EMAIL PROTECTED]> ha scritto:
> .> > > > >
> .> > > > > "Cristiano" <[EMAIL PROTECTED]> wrote in message
> .> > > > > news:9gimtg$d4d$[EMAIL PROTECTED]...
> .> > > > Now I changed the generator in this way:
> .> > > > 1) I fill a 256 bits vector with 8 pseudorandom 32 bits numbers;
> .> > >
> .> > > Careful here. You should typically bring in more bits then you put
> out.
> .> > > This is because you want to make sure the amount of entropy comming
> in
> .> is
> .> > > sufficient. Let's say you bring in 256 bits from say the mouse
> .> > co-ordinates
> .> > > [the lsbs]. But there is a huge skew of say p=0.95 for 1 in the
lsb,
> .> this
> .> > > means your 256 bits has only -256 * log2(0.95) = 19 bits of real
> .> entropy.
> .> > > You would need 3460 bits to get your 256 bits of entropy.
> .> >
> .> > Is there any empirical method that allows me to calculate how much do
> bits
> .> > need?
> .>
> .> Typically with bits you can do say an 10-th order adaptive predictor.
> I.e
> .> given the past 10 bits, what is more likely to come?
> .>
> .> If your data is truly random it will be 0.5/0.5 either way. So you
train
> .> the model on your data [you will need a lot of data, say 50,000 bits at
> .> least] then for each new bit you add the entropy. If for example you
> have
> .> 0000011111 0, given the ten bits 0000011111 you look up in the model
> which
> .> is more likely to occur 0 or 1. Let's say P(1) = 0.95, then we know
that
> .> only -log2(0.95)=0.07 bits were added to the output.
>
> I am a bit confused. I don't understand how you can say "[...] P(1)=0.95".
> If my sequence is 0101010001111011, how much big is the entropy?
Do this
int counts[2][1024], state=0;
float entropy_bit(int bit)
{
float p;
counts[0][state] += bit;
++counts[1][state];
p = counts[0][state] / counts[1][state];
if (!bit) p = 1.0 - p;
p = -log(p) / log(2.0);
state <<= 1;
state |= bit;
state &= 1023;
return p;
}
If this is correct, it should give you the 10-th order prediction of the
output.
Feed say 50,000 bits from your seed material [not the PRNG output] thru
this. Then feed another 100 bits. In the last 100 bits keep a sum of the
output of entropy_bit() [ignore the return value for the first 50,000 bits].
Note: This is not the only test in the world. In fact it's possible to pass
this and still be insecure.
Tom
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: survey
Date: Mon, 18 Jun 2001 22:11:20 +0200
Benjamin Goldberg wrote:
>
> Douglas A. Gwyn wrote:
> >
> > Mok-Kong Shen wrote:
> > > Would you please explain a bit on the meaning of 'stream
> > > ciphers that are not of the key-generator class'?
> >
> > Basically, there is no subsystem that generates a
> > plaintext-independent key which is then combined
> > with the plaintext in a totally separate subsystem.
> >
> > Note that when I phrase it that way, it is evident
> > what some weaknesses might be in key-generator
> > based systems.
>
> Dynamic Transposition?
One could use a key stream to do both transposition and
substitution and have feedback to influence the key
generation process.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Q: XML-security
Date: Mon, 18 Jun 2001 22:11:14 +0200
I read somewhere an article stating that the possibility
in the new standard for XML-security of user selective determination of
parts of an XML document to be encrypted
is essential, for otherwise one could encrypt only the
whole document and that would be bad for security. Could
someone explain why the encryption of the whole document
is bad in clear-cut terms? Thanks in advance.
M. K. Shen
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: survey
Date: Mon, 18 Jun 2001 16:24:21 -0400
Douglas A. Gwyn wrote:
[snip]
> Either you refuse to try to understand, or you don't understand
> the role of counterexamples in reasoning. Either way, you lose.
>
> I suspect many other people understood the point, which could
> have been made verbosely thus: "Simplicty and speed are minor
> matters for a cryptosystem compared to its resistance to attack."
Then a counterexample to your point coule be:
Take all the ciphers you know. Generate independent keys for each.
Encipher each block of data with every cipher.
Surely this system is highly resistant to attack, but, it's neither
simple nor fast. I wouldn't use it. I would go with AES [which is
simple, fast, and secure], rather than this. For that matter, from a
POV purely of strength, Serpent beats Rijndael... why was Rijndael
chosen instead for AES? Speed and simplicity.
--
The longer a man is wrong, the surer he is that he's right.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: survey
Date: Mon, 18 Jun 2001 22:17:29 +0200
Benjamin Goldberg wrote:
>
> Douglas A. Gwyn wrote:
> [snip]
> > Either you refuse to try to understand, or you don't understand
> > the role of counterexamples in reasoning. Either way, you lose.
> >
> > I suspect many other people understood the point, which could
> > have been made verbosely thus: "Simplicty and speed are minor
> > matters for a cryptosystem compared to its resistance to attack."
>
> Then a counterexample to your point coule be:
> Take all the ciphers you know. Generate independent keys for each.
> Encipher each block of data with every cipher.
>
> Surely this system is highly resistant to attack, but, it's neither
> simple nor fast. I wouldn't use it. I would go with AES [which is
> simple, fast, and secure], rather than this. For that matter, from a
> POV purely of strength, Serpent beats Rijndael... why was Rijndael
> chosen instead for AES? Speed and simplicity.
I suppose that the context of the quote you commented on
previously was not that of finding the practically best
encryption.
M. K. Shen
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Counter mode, the better way to do it?
Date: Mon, 18 Jun 2001 20:27:45 GMT
"Tim Tyler" <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> : "Julian Morrison" <[EMAIL PROTECTED]> wrote in message
> :> Two approaches I've seen to doing CNT mode for Rijndael:
>
> :> - use the raw count, say a 32 bit unsigned int in one quad of bytes and
> :> the 12 remaining bytes as 0x00. [...]
> :>
> :> - feed the count through a scrambling function first, such as MD5.
> :>
> :> Which is safer and better?
>
> : In a good cipher.....neither.
>
> I presume that use of a hash would help eliminate the CTR mode proviso
> that you change keys before you've transmitted sqrt(2^blocksize) blocks.
I don't see how the birthday paradox applies to this case. Pairs of known
texts will not lead to knowing the output as far as I know.
> Note also that use of two cryptographic primitives might be seen as
> slowing things down somewhat.
>
> As Tom says, if your cypher's OK, there's no need to worry about the known
> plaintext.
Bingo.
> However if you *do* want to avoid it, you could do something like instead
> of adding 1, add an odd constant with roughly the same number of 1 and 0
> bits set in it, and rather than padding with 0s, duplicate the counter
> across the block size. These are not expensive operations to perform -
> in contrast to hashing - which has a large cost.
Adding a constant doesn't change the situation much from the naive pov. The
attacker still knows the inputs.
Tom
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: "computationally impossible" and cryptographic hashs
Date: Mon, 18 Jun 2001 16:36:34 -0400
Henrick Hellström wrote:
[snip]
> For example, a 128-bit block cipher belongs to the set of functions
> {0,1}^128 -> {0,1}^128. This set contains (2^128)^(2^128) elements.
Sorry, no. Block ciphers need to be invertable, and hence bijective.
Since they're bijective functions with the domain and codomain the same,
they are permutations. The set of permutations on {0,1}^128 is size
((2^128)!), not (2^128)^(2^128). However, this is still a mind-
bogglingly huge number, so the rest of your argument holds true.
--
The longer a man is wrong, the surer he is that he's right.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: XOR256 encryption/decryption method
Reply-To: [EMAIL PROTECTED]
Date: Mon, 18 Jun 2001 20:15:06 GMT
George Anescu <[EMAIL PROTECTED]> wrote:
: Recently I played with some encryption ideas and the results with
: source code are presented in two articles with codeproject.com:
: http://www.codeproject.com/useritems/filecrypt.asp
Unless I'm mistaken you're using an LCG to create a random stream
and XORing it with your plaintext.
LCGs are not secure.
There appear to be some subsequent attempts to introduce complications -
but the fact that an LCG is being employed is extremely worrying.
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
Date: 18 Jun 2001 20:28:35 -0000
From: [EMAIL PROTECTED]
Subject: Sorry, I didn't know that was considered "spam"
Hey!
I want to apologize to all those I offended (or just plain
pissed-off!) with all the fake submissions to mailing lists
(i.e., BOMP) and other people's web-boards - as well as to all
the coolest-sounding Usenet newsgroups - about my project, 'thee
Wytches'.
I thought it would be fun to act like this was an unearthed
discovery of a lost classic - and mysterious - band. I figured
people would enjoy the game.
Guess not.
I thought Usernet was simply a place to post any messages,
anywhere - and not the forum for specific-interest discussion
that I have since been shown that it is.
I am Formerly Unclear on the Usernet Concept.
Hey, stop by my websites, and I'll make it up to ya!
They're FREE today - and you can sign my guest books:
thee Wytches (displays poster IP)
http://www.tiac.net/users/mrobin/wytches/cgi-bin/wytchboard.pl
and
Zombie Au Go-Go! (accepts HTML!)
http://www.tiac.net/users/mrobin/cgi-bin/dispbook.pl
Some of the comments you'll see there are pretty nonsensical.
Sorry about that. I just did some free-association stuff in
place of all the complaints people had posted regarding my
little faux pas.
Again, I'm really sorry about any offense.
Stop on by, right now! Get to know The Real Me (not the
clueless spammer) and have some yogurt!
Let me know what you REALLY think about spam. And - oh yeah! -
about my ideas for my "band" project ;)
Thanks for listening.
PS *Sometimes* the website scripts are flaky because of my ISP,
and you can't get in, for example, to post messages to the
guestbooks. If that does happen to you (first, thanks for
visiting, and for at least trying!) PLEASE let me know with an
email, so I have the documentation to hand over to my provider.
I love you.
--
Mark Robinson (de-Cloaked!)
[EMAIL PROTECTED]
Teenbeat Records: http://www.teenbeatrecords.com
Previous Postings Archive
(My "Spam"):
http://groups.google.com/groups?q=%22thee+Wytches%22
------------------------------
Reply-To: "Henrick Hellström" <[EMAIL PROTECTED]>
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Mon, 18 Jun 2001 20:37:14 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> Henrick Hellström wrote:
> >
> > See http://www.streamsec.com/createsc.asp The proof is incuded. I
> > suppose that's where you got the idea in the first place.
>
> No, I got the idea to create single-cycle sboxes in this manner from the
> key schedule of the LJA1 cipher, which predates your code significantly.
>
> And I'm sure that he got his code from somewhere else. Don't try to
> steal credit from others.
I don't try to steal credit from anyone. You had a look at Steak some week
before you posted that message, and I simply wanted to hear if you had some
further questions or comments regard that cipher.
> > temp := a permutation of length n-1.
> > J := n-1;
> > for I := 0 to n-2 do begin
> > X := temp[I];
> > SBox[J] := X;
> > J := X;
> > end;
> > SBox[J] := n-1;
>
> This looks almost exactly like mine, offset by 1.
>
> Mine [with the typos corrected] is:
> temp = random_permutation
> for( i = 0 to N-2 )
> sbox[ temp[i] ] = temp[i+1];
> sbox[ temp[N-1] ] = temp[0];
>
> Yours is equivilant to:
> temp = random_permutation
> for( i = 0 to N-2 )
> sbox[ temp[i-1 % N] ] = temp[i];
> sbox[ temp[N-2] ] = N-1;
>
> With the difference being that mine is correct. Yours has N-1 where it
> should have temp[N-1]. Is this a typo? And if one is bothering to use
> a temp value like your J value, then the last assignment can be gotten
> rid of:
> temp = random_permutation
> j = temp[N-1];
> for( i = 0 to N-1 )
> j = sbox[ j ] = temp[i];
>
> But I wouldn't write psuedocode like this, as it's not as clear what
> it's supposed to be doing.
You're missing something. Any cycle of length N can be written in N
different ways, each way corresponding to a rotation of the cycle.
Consequently, you can fix one value at a certain position of the cycle, and
use key data only to position the rest of the N-1 values. My algorithm fixes
value N-1 at position N-1. That's no error, and that's why the algorithm
doesn't result in any collisions.
The J variable is there because it would most likely be there in any
implementation, provided that the compiler stores it in a CPU register and
not on the stack.
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: decorrelated bitsliced cipher
Date: Mon, 18 Jun 2001 16:50:46 -0400
Tom St Denis wrote:
>
> "Simon Johnson" <[EMAIL PROTECTED]> wrote in message
> news:9eh6b0$16$[EMAIL PROTECTED]...
> > > This cipher could be fast. In fact cool idea. Make a 64-bit
> > > block cipher using eight bytes and doing GF mults in GF(2^8) and
> > > some linear transform that would rotate and shift the bytes
> > > around.
> > >
> > > What do you guys/gals think?
> > >
> > > Tom
> > >
> > Ace.. should be quite fast.. I'd keep the GF mults down to 2^4
> > though keeps the speed up...
>
> Well that's the tradeoff. The bigger the field the more resistance
> you get.
>
> With GF(2^4) a mult takes four iterations of the main loop. You can
> do shifts by just moving words from one place to another, etc..
>
> I have some C code todo this if you care to see.
If you're clever, you might not even need to move the words around to do
the shifts... just leave them in place, and *pretend* they've been moved
around by adding to their indices. This might only work if you unroll
your loops, though [I'm not sure].
--
The longer a man is wrong, the surer he is that he's right.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: decorrelated bitsliced cipher
Date: Mon, 18 Jun 2001 20:47:09 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > "Simon Johnson" <[EMAIL PROTECTED]> wrote in message
> > news:9eh6b0$16$[EMAIL PROTECTED]...
> > > > This cipher could be fast. In fact cool idea. Make a 64-bit
> > > > block cipher using eight bytes and doing GF mults in GF(2^8) and
> > > > some linear transform that would rotate and shift the bytes
> > > > around.
> > > >
> > > > What do you guys/gals think?
> > > >
> > > > Tom
> > > >
> > > Ace.. should be quite fast.. I'd keep the GF mults down to 2^4
> > > though keeps the speed up...
> >
> > Well that's the tradeoff. The bigger the field the more resistance
> > you get.
> >
> > With GF(2^4) a mult takes four iterations of the main loop. You can
> > do shifts by just moving words from one place to another, etc..
> >
> > I have some C code todo this if you care to see.
>
> If you're clever, you might not even need to move the words around to do
> the shifts... just leave them in place, and *pretend* they've been moved
> around by adding to their indices. This might only work if you unroll
> your loops, though [I'm not sure].
Hmm. I dunno if doing the decorrelation would be fast. It would be better
than fixed sboxes though.
Another problem is that you have to find inverse sboxes for each round. Of
course you can brute force the inverses in parallel by doing some
mult-squares.
Another problem is you must ensure that each mult is non-zero. One way ...
if we name all four words A,B,C,D is todo A = A | ~(A|B|C|D);
Tom
------------------------------
Reply-To: "Henrick Hellström" <[EMAIL PROTECTED]>
From: "Henrick Hellström" <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Mon, 18 Jun 2001 20:48:39 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> ... And if one is bothering to use
> a temp value like your J value, then the last assignment can be gotten
> rid of:
> temp = random_permutation
> j = temp[N-1];
> for( i = 0 to N-1 )
> j = sbox[ j ] = temp[i];
Oh, that's one of the reasons why I strongly discourage anyone from using C.
;-)
One line double assignments like that aren't logical and tend to result in
extremely messy code (in particular if they are mixed with post/pre
in/decrements). In my opinion, an assignment is an instruction and not an
expression. If it should have any value at all, it should be the address of
the code it corresponds to.
But this is getting OT....
--
Henrick Hellström [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Single-cycle sbox question
Date: Mon, 18 Jun 2001 20:52:51 GMT
"Henrick Hellström" <[EMAIL PROTECTED]> wrote in message
news:HOtX6.1433$[EMAIL PROTECTED]...
> "Benjamin Goldberg" <[EMAIL PROTECTED]> skrev i meddelandet
> news:[EMAIL PROTECTED]...
> > ... And if one is bothering to use
> > a temp value like your J value, then the last assignment can be gotten
> > rid of:
> > temp = random_permutation
> > j = temp[N-1];
> > for( i = 0 to N-1 )
> > j = sbox[ j ] = temp[i];
>
>
> Oh, that's one of the reasons why I strongly discourage anyone from using
C.
> ;-)
Why? You can write bad code in any language.
> One line double assignments like that aren't logical and tend to result in
> extremely messy code (in particular if they are mixed with post/pre
> in/decrements). In my opinion, an assignment is an instruction and not an
> expression. If it should have any value at all, it should be the address
of
> the code it corresponds to.
Not really...
a=b=c=d=e=f=g=0;
Much better than
a=0;
b=0;
c=0;
d=0;
e=0;
f=0;
g=0;
Tom
------------------------------
** 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
******************************
