Cryptography-Digest Digest #568, Volume #11 Mon, 17 Apr 00 19:13:01 EDT
Contents:
Re: GOST idea (Mok-Kong Shen)
Re: Paper on easy entropy (Mok-Kong Shen)
Re: Documentation Standards (Mok-Kong Shen)
Re: GOST idea (Tom St Denis)
Re: Requested: update on aes contest (Anton Stiglic)
Re: DES KEY Scheduling (Richard Heathfield)
Re: Q: source code for recognizing English (Jim Gillogly)
Re: Advice in my situation (Newbie) (Pat Caudill)
Re: Paper on easy entropy (Tom St Denis)
Re: Should there be an AES for stream ciphers? (John Savard)
Re: Miami Herald article about ATM ripoffs (Ron Yaklime)
Re: Paper on easy entropy (Andru Luvisi)
Re: Requested: update on aes contest (Scott Contini)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: GOST idea
Date: Tue, 18 Apr 2000 00:11:44 +0200
Tom St Denis wrote:
>
> Mok-Kong Shen wrote:
> > As far as I understand, it is very important to examine the
> > avalanche property of one single round very carefully. For many
> > rounds, one can heuristically expect a better effect. But if
> > you compare two different S-boxes, you have to look whether
> > the one is superior to the other in one round, for otherwise
> > your are likely to get confused by your data for many rounds,
> > I am afraid.
>
> Well the quadratic is just a bijective function of the input, much like
> the S() function (sbox substitution). So at the worst it will not
> increase the avalanche. But the amount of active sboxes in GOST grows
> quite slowly. I have found with the quadratic it doesn't take as long
> to increase the active sboxes.
I have in a previous post explained why one can't unconditionally
expect that it wouldn't give a worse result. (There w1 and w2,
differing in more than one bit, may be such that their avalanche
effects cancel out.) You have either to theoretically show that
or do sufficient amount of experiments as I mentioned earlier.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Paper on easy entropy
Date: Tue, 18 Apr 2000 00:11:54 +0200
Tom St Denis wrote:
>
> Order-0 means I evalutate the probability of each symbol in the 'zero'
> context, which means I don't care about preceding chars. An order-1
> model is more accurate. For example the letter 'h' is not fairly
> probable, but it's more probable after a 't'. So if the preceding char
> was a 't' and we are on a 'h' now it's not very random.
Is that 'probability' equal to the frequency of the symbols in
the 'particular' sequence whose entropy you are determining?
If yes, why don't you just take the text from a book or books to
obtain the desired entropy? If not, would you please explain how
you determine that 'probability'?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Documentation Standards
Date: Tue, 18 Apr 2000 00:11:49 +0200
Guy Macon wrote:
>
> I wrote a document this week that addresses this issue. I would be
> most appreciative if anyone chooses to comment - especially to point
> out any stupid blunders I may have made.
I don't think anyone would object what you desire to do in your
engineering project. You certainly have put in much good
intellectual effort in that. However, much discussion in this
thread was centered round in which format and where informations
that are intended for readers of this group should be put. I like
to repeat my view that the best is to post directly to this group
in ASCII, if the volume is small, otherwise in (standard) HTML
on one's web page, so that nobody needs to have to get any tools to
read the file in any other format like ps or pdf, which takes
also more volume than HTML for the transmission. (One can also
offer download of an ASCII file.)
M. K. Shen
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: GOST idea
Date: Mon, 17 Apr 2000 22:29:54 GMT
Mok-Kong Shen wrote:
>
> Tom St Denis schrieb:
> >
> > Mok-Kong Shen wrote:
> > >
> > > Tom St Denis wrote:
> > > >
> > > > Mok-Kong Shen wrote:
> > >
> > > > > > Maybe I misunderstood. My point is the following: If v is the
> > > > > > input and w the output and one knows that between v and w there
> > > > > > is a certain avalanche property, i.e. the effect of flipping
> > > > > > one bit of v. Now suppose I have a mapping of u to v that is a
> > > > > > permutation. Two values u1 and u2 differing only in one bit
> > > > > > may have the corresponding values v1 and v2 differing in many
> > > > > > bits and their resulting effect on a comparison between w1 and
> > > > > > w2 may not be simple to tell.
> > > > >
> > > > > Addendum:
> > > > >
> > > > > Could you please give a literature reference to the fact that
> > > > > the function you gave previously is a permutation?
> > > >
> > > > 2x^2 + x mod 2^w is a permutation polynomial of x. Hmm I got the idea
> > > > from a paper on Rivest's site, and I can email a copy if you want.
> > >
> > > But in your post of 16th April you said you are working in GF(2^w).
> > > Now GF(2^w) has characteristic 2, so 2x^2 = 0, if I don't err.
> >
> > Actually no it doesn't. modulo 2^w, 2x^2 + x is always a permutation
> > polynomial.
>
> Note that you are NOW talking of modulo 2^w. As I pointed out,
> you were instead talking of GF(2^w) in the post where you first
> mentioned that the function is meant to be a permutation! (Thus I
> was quite surprised and asked you to give references to support
> that claim.) Do you see my point?
Yea, sorry bout that. So you say GF(2^w) when the polynomial itself is
taken modulo that?
Tom
------------------------------
From: Anton Stiglic <[EMAIL PROTECTED]>
Subject: Re: Requested: update on aes contest
Date: Mon, 17 Apr 2000 18:38:38 -0400
This is a multi-part message in MIME format.
==============176F4380A8DE34413CFB110D
Content-Type: text/plain; charset=us-ascii
Content-Transfer-Encoding: 7bit
Well I could maybe say a word or two.
I went to FSE and AES3 last week in New York. It was the first time
I had been in a conference that discusses about symmetric encryption.
I have a few taughts...
So first of all, everybody knows that there are 5 ciphers remaining for
AES
Serpent (Ross Anderson, Knudsen, Biham)
Mars (Coppersmith, Gennaro, Matyas and others from IBM)
Rijndael (Rijmen and Daemen)
RC6 (Rivest, Robshaw, Sidney and Yin)
Twofish (Schneier, Kelsey, Whiting, Wagner, Hall and Ferguson)
None of them have been obviously broken. Attacks that where
presented against these 5 ciphers necessitate extreme amounts
of memory and/or computation, and the attacks where just slightly
better than brute force, and this on a limited number of rounds.
What amazed me is the slim amount of people that are actually
working on breaking these ciphers, all the interesting attacks
came from either the Twofish team (or extended Twofish team)
or from Knudsen or Biham or Lucks. The Mars, Rijndael and RC6
team seemed to have not invested much effort in cryptanalysis.
Interestingly enough, the only cipher that has not been attacked
is Twofish.
There were allot of performance analyses presentations.
Performance analyses on software (ANSI C, assembly, Java, on
different architectures), smartcards and FPGA (Field programmable
Gate Arrays).
There was allot of inconsistency between groups who programmed
in the same environment, mostly du to the fact that they selected
different optimization techniques or the fact that some groups were
not aware of some optimization techniques the authors of the ciphers
proposed or had in mind. Averaging everything out, Mars seemed
to have the weakest performance on all platforms (Mars got a good
banging at FSE and AES), RC6 came second in the poor performance
area even dough they have the most elegant, and shortest, algorithm.
Interestingly, the code that the authors of the ciphers delivered to
NIST at the time they submitted their candidature was analyzed for
performance by NIST, all of them did bad (RC6 and Rijndael came up
on top) and the results where totally inconsistent with all the other
analysis that were presented (I'm guessing that this is du to the fact
that the cipher submiters just don't know how to code :).
There was some concern expressed about patent attacks, some felt that
this is a serious valid attack that might occur against AES. It is
based on the
fact that some of the proposed candidates use "new" primitives that
might be
patented. NIST is doing some research in this area.
There was also some talk about NIST choosing more than one AES
candidate.
Most everybody was against choosing more than 1, based on these facts
- higher probability of patent attack
- less interoperability (ex.: if one is using Serpent because it's fast
on
cards, and wants to interoperate with some software that implemented
Twofish....)
- harder to implement (smartcard has limited resources
- confusion: if crypto community can't decide on which cipher to use,
who can?
Some suggested NIST choose one cipher plus one back up, some counter
arguments to that were:
- The ciphers seem equally secure against todays technology, and are
(for the most part) based on the same principals. If any one of the
AES
candidates were to be broken, one should re-analyse all of them.
The greatest part of the whole conference was definitely the end, where a
representative of each team had a chance to explain why his cipher is
better than the others, it was fun.
So that's about it, I personally had allot of fun, met allot of interesting
people
and learned a couple of things.
Anton
==============176F4380A8DE34413CFB110D
Content-Type: text/x-vcard; charset=us-ascii;
name="anton.vcf"
Content-Transfer-Encoding: 7bit
Content-Description: Card for Anton Stiglic
Content-Disposition: attachment;
filename="anton.vcf"
begin:vcard
n:Stiglic;Anton
x-mozilla-html:FALSE
org:Zero-Knowledge Systems Inc;Security dev. team.
adr:;;;;;;
version:2.1
email;internet:[EMAIL PROTECTED]
title:Crypto Punk
x-mozilla-cpt:;0
fn:Anton Stiglic
end:vcard
==============176F4380A8DE34413CFB110D==
------------------------------
Date: Mon, 17 Apr 2000 23:38:15 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: DES KEY Scheduling
Karim A wrote:
>
> Hi all,
>
> I'm implementing the des algorithm,
> And I'd like someone explains me how to perform the key scheduling.
> Once I've a 56 bits key, how should I perform the left shift with the 2* 28
> bits ?
> What kind of data type should I use ?
> Can someone give me a "clear" piece of source code ?
>
> Thanks,
>
> best regards ;o)
>
> Karim
You don't say what language you're coding in, so I'll just have to do my
best.
In C (and C++) it's easy to shift left.
a = b << c; /* shift b left by c bits, storing the result in a */
b <<= c; /* shift b left by c bits, storing the result in b */
In BASIC, you have (I think) to multiply by 2, as there is no specific
shift operator IIRC:
A = B * (2 ** C); /* shift b left by c bits, storing the result in a */
Pascal? Foo - no idea.
As for a data type, if you're doing this in C, it's important to use
unsigned types when you're mucking about with bits, if you want your
code to work on other platforms. unsigned long is guaranteed to be good
for 32 bits, and can be longer on some platforms.
You might prefer to use some pre-canned code. I posted some C code here
recently, in the thread "Why is this algorithm insecure? (Newbie
flamefodder)". In it, you'll find C code to manipulate an array of bits
(using unsigned char for the datatype), rotating it either left or
right, as you like. (One function for each direction.)
Pay no attention to the cryptography in that code - I know considerably
less about cryptography than you do, I suspect - but there's nothing
wrong with my bit rotation functions, I promise you (but if Doug Gwyn
laughs in my face, listen to him, not me...).
Of course, they do /rotate/ bits, rather than shift them, so you might
need to clear out some bits when you're done, but that's not hard, given
the macros I stole from www.snippets.org.
[This advice offered partly by way of thanks to sci.crypt for not
flaming me to a crisp over the weekend.]
I can't help with the 'key scheduling', as I don't know what that is.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
29 K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html (68
to go)
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Q: source code for recognizing English
Date: Mon, 17 Apr 2000 22:51:06 +0000
"Douglas A. Gwyn" wrote:
>
> [EMAIL PROTECTED] wrote:
> > ... frequencies of letters, double-letters (ll,ss,ee,oo),
> > triple letters, ... I have some difficulties though.
>
> The usual biggest problem with such an approach is the
> assignment of zero likelihood to a trial when it contains
> an "impossible" digraph or trigraph. There are theoretical
> solutions to this problem, dating back to an article by Good
> in Biometrika around 1940, or you can use a simpler method
> as in MilCryp, although the latter doesn't work well when
> too many of the cells of the expected-frequency matrix had
> to be fudged.
It's easier to get lots of data for your counts in these days
of mega-text on the Net. For example, my tetragraph file,
compiled from Gutenberg, OTA, and Usenet a few years ago,
has about 1/4 of the half-a-million possible tetragraphs
populated with a non-zero value.
I use it by adding a sort of binary log of the frequency for
each "hit" in a tentative plaintext, rather than treating it
as a strict probability, where it goes to 0 if you hit an empty
cell. That way you can use it to improve your text gradually
in a hill-climbing program.
--
Jim Gillogly
Mersday, 27 Astron S.R. 2000, 22:46
12.19.7.2.7, 12 Manik 10 Pop, Second Lord of Night
------------------------------
From: Pat Caudill <[EMAIL PROTECTED]>
Subject: Re: Advice in my situation (Newbie)
Date: Mon, 17 Apr 2000 15:48:49 -0700
On Fri, 14 Apr 2000 1:59:42 -0700, Francois Grieu wrote
(in message <[EMAIL PROTECTED]>):
> A reasonably good method to generate the certificate would be to have an
> (as much as possible) secret key (16 byte of data you deeply hide in you
> code) and use the MD5 algorithm on the concatenation of the key and the
> high score record:
> certificate = MD5(key|score) NB: | denotes concatenation
> or even safer
> certificate = MD5(MD5(key|score)|key)
Would it be better to apply the MD5 to the concatenation of the score and the
whole program? that way it would be harder to modify the program.
Pat Caudill
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Paper on easy entropy
Date: Mon, 17 Apr 2000 22:59:39 GMT
Mok-Kong Shen wrote:
>
> Tom St Denis wrote:
> >
>
> > Order-0 means I evalutate the probability of each symbol in the 'zero'
> > context, which means I don't care about preceding chars. An order-1
> > model is more accurate. For example the letter 'h' is not fairly
> > probable, but it's more probable after a 't'. So if the preceding char
> > was a 't' and we are on a 'h' now it's not very random.
>
> Is that 'probability' equal to the frequency of the symbols in
> the 'particular' sequence whose entropy you are determining?
> If yes, why don't you just take the text from a book or books to
> obtain the desired entropy? If not, would you please explain how
> you determine that 'probability'?
The user types random chars like "dfkhthegolhsflgkeoguig". Then I count
the occurences of each char, then I use that #/#ofchars as the
probability of each char.
I can't train the model after abook since that's hardly random.
Tom
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Should there be an AES for stream ciphers?
Date: Mon, 17 Apr 2000 22:52:43 GMT
Albert Yang <[EMAIL PROTECTED]> wrote, in part:
>Thoughts? AES Stream Cipher just a waste of time? While on the
>subject, why not have a AES Hash contest too?
For the hash, they're just letting the NSA do it. (The SHA-2 thread)
Bruce Schneier expressed interest in having an AES for stream ciphers,
on the basis - as I understood it - that they can be more efficient
for the same level of security, and CPU cycles are a big concern among
many encryption users.
It would not be a waste of time, therefore, in the opinion of some of
the experts. But the AES process is being done to meet the needs of
the Federal Government, and block ciphers are, at least in certain
ways, better understood in the open community, so there is (or there
is percieved to be) less chance of a standard turning out to be weak
in some way we don't understand yet than with a stream cipher -
perhaps. The rationale may have been completely different.
John Savard (jsavard<at>ecn<dot>ab<dot>ca)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Ron Yaklime)
Subject: Re: Miami Herald article about ATM ripoffs
Date: Mon, 17 Apr 2000 23:05:23 GMT
"Mark McCarthy" <[EMAIL PROTECTED]> wrote:
>I don't know how much of this is proprietary so I won't go too deep.
I wrote:
>Why not? What country do you live in? What are you afraid of?
[EMAIL PROTECTED] (Mike Andrews) wrote:
>He may have signed a Non-Disclosure Agreement with his employer
>or with a third party, such that he is limited in what he can
>disclose to people who aren't covered by the NDA.
I doubt it. If that was the case then he would presumably know how much of
it was proprietary. I suspect that he thinks that if a company declares
something "proprietary" then this declaration overrides freedom of speech
and obligates everyone in the country to guard that company's secrets.
--
"Ron Yaklime" is actually 8759 243610 <[EMAIL PROTECTED]>.
012 3456789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: Paper on easy entropy
Date: 17 Apr 2000 16:02:32 -0700
Tom St Denis <[EMAIL PROTECTED]> writes:
> I wrote a mini paper discussing a method of extracting entropy from the
> keyboard. It's at
>
> http://24.42.86.123/files/entropy.ps
>
> In case anyone cares to read it.
>
> Tom
Could you post a plaintext or html version for those of us who use
terminals?
Andru
--
==========================================================================
| Andru Luvisi | http://libweb.sonoma.edu/ |
| Programmer/Analyst | Library Resources Online |
| Ruben Salazar Library |-----------------------------------------|
| Sonoma State University | http://www.belleprovence.com/ |
| [EMAIL PROTECTED] | Textile imports from Provence, France |
==========================================================================
------------------------------
From: [EMAIL PROTECTED] (Scott Contini)
Subject: Re: Requested: update on aes contest
Date: 17 Apr 2000 23:08:06 GMT
In article <[EMAIL PROTECTED]>, Anton Stiglic <[EMAIL PROTECTED]> wrote:
>This is a multi-part message in MIME format.
>--------------176F4380A8DE34413CFB110D
>Content-Type: text/plain; charset=us-ascii
>Content-Transfer-Encoding: 7bit
>
>Well I could maybe say a word or two.
>
>I went to FSE and AES3 last week in New York. It was the first time
>I had been in a conference that discusses about symmetric encryption.
>I have a few taughts...
>
>So first of all, everybody knows that there are 5 ciphers remaining for
>AES
> Serpent (Ross Anderson, Knudsen, Biham)
> Mars (Coppersmith, Gennaro, Matyas and others from IBM)
> Rijndael (Rijmen and Daemen)
> RC6 (Rivest, Robshaw, Sidney and Yin)
> Twofish (Schneier, Kelsey, Whiting, Wagner, Hall and Ferguson)
>
>None of them have been obviously broken. Attacks that where
>presented against these 5 ciphers necessitate extreme amounts
>of memory and/or computation, and the attacks where just slightly
>better than brute force, and this on a limited number of rounds.
>What amazed me is the slim amount of people that are actually
>working on breaking these ciphers, all the interesting attacks
>came from either the Twofish team (or extended Twofish team)
>or from Knudsen or Biham or Lucks. The Mars, Rijndael and RC6
>team seemed to have not invested much effort in cryptanalysis.
>Interestingly enough, the only cipher that has not been attacked
>is Twofish.
>
>There were allot of performance analyses presentations.
>Performance analyses on software (ANSI C, assembly, Java, on
>different architectures), smartcards and FPGA (Field programmable
>Gate Arrays).
>There was allot of inconsistency between groups who programmed
>in the same environment, mostly du to the fact that they selected
>different optimization techniques or the fact that some groups were
>not aware of some optimization techniques the authors of the ciphers
>proposed or had in mind. Averaging everything out, Mars seemed
>to have the weakest performance on all platforms (Mars got a good
>banging at FSE and AES), RC6 came second in the poor performance
>area even dough they have the most elegant, and shortest, algorithm.
>
>Interestingly, the code that the authors of the ciphers delivered to
>NIST at the time they submitted their candidature was analyzed for
>performance by NIST, all of them did bad (RC6 and Rijndael came up
>on top) and the results where totally inconsistent with all the other
>analysis that were presented (I'm guessing that this is du to the fact
>that the cipher submiters just don't know how to code :).
The timings that NIST did at the AES2 conference were a bit strange -
it was something like encrypting one block of data 1000 times. This,
in my opinion, was not a good measure of the true speed of the cipher,
since it included the overhead for the API. I suggested to them that
they redo the timings by instead encrypting several thousand blocks
multiple times and averaging the times. They never replied to my
request. I wonder how they did their timings this time.
Thanks for the update - I wish I could've attended the conference!
Scott
------------------------------
** 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
******************************
