Cryptography-Digest Digest #704, Volume #12 Mon, 18 Sep 00 00:13:01 EDT
Contents:
Re: A Degree in Encryption (Mack)
Re: Serpent S-boxes (again) (Mack)
Re: Tying Up Loose Ends - Correction (John Savard)
Re: Tying Up Loose Ends - Correction (John Savard)
Re: Tying Up Loose Ends - Correction (John Savard)
Re: question about delastelle cipher in Bauer's book (John Savard)
Re: Serpent S-boxes (again) (Terry Ritter)
Re: Serpent S-boxes (again) (Tom St Denis)
Re: SDMI Crypto Challenge (Tom St Denis)
Re: One-way encryption (Tom St Denis)
Re: Music Industry Offers US$10K for cracking their encryption system (Tom St Denis)
Re: A Degree in Encryption (David A Molnar)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mack)
Subject: Re: A Degree in Encryption
Date: 18 Sep 2000 01:28:23 GMT
>Hi
>
>I am looking for info as to what is the best, or proper university to enroll
>for a phd in encryption. I have a degree in computer engineering and
>currently working on MBA. I also have a ten yr working experience.
>
>Any help on this will be highly appreciated.
>
>Best Regards
>
You have a pretty good choice of fields to get a degree in.
Number Theory, Information Science, Information Theory ...
But I don't know of a university that offers a degree program specifically
in encryption.
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (Mack)
Date: 18 Sep 2000 01:48:56 GMT
Subject: Re: Serpent S-boxes (again)
>
>On 17 Sep 2000 16:21:43 GMT, in
><[EMAIL PROTECTED]>, in sci.crypt
>[EMAIL PROTECTED] (Mack) wrote:
>
>>>[EMAIL PROTECTED] wrote:
>>>: [EMAIL PROTECTED] (Gregory G Rose) wrote:
>>>
>>>:> I guess this could be considered an example of "proof by assertion",
>>>:> but, has anyone actually checked the stated algorithm to see if it
>>>:> does produce the chosen s-boxes?
>>>
>>>: The algorithm presented in the serpent paper is not complete they have
>>>: a step labeled "test for given criteria" which doesn't say "how" the
>>>: tests are done.
>>>
>>>*If* the criteria are well defined, it shouldn't matter how the tests are
>>>done. For example, "non-linearity of 4" should be unambiguous, no matter
>>>how you do your tests.
>>
>>In that specific case there are a number of measures of non-linearity.
>>So it isn't really a well defined criteria.
>
>I basically dispute this. Yes, it is true that Boolean function
>nonlinearity is applied to "bit-columns" in substitutions. This gives
>a nonlinearity result for each column, which are then often combined
>in some way. Typically we use either the minimum or the mean, and I
>have used both.
>
>Developing two related results from exactly the same set of Boolean
>function nonlinearity data hardly constitutes "a number of measures."
>
The idea of non-linearity is pretty straight forward but the specific
phrase "a non-linearity of four" is ambiguous.
Does it mean minimum maximum or mean. In this case I believe it is
minimum distance to the set of affine functions. It could also
mean the sum of distances to affine funtions as has been used
in the past.
>
>It is also true that "nonlinearity" originally implied a Fourier
>transform of data. I speculate that this form in fact may be more
>useful in the context of RNG's and stream ciphers.
>
>But for the past decade, s-box analysis has almost exclusively used
>the Walsh-Hadamard transform (and correlation to the related "affine
>Boolean functions" as opposed to sine waves of different frequency)
>for Boolean function analysis.
>
>I would be most glad to receive any citations or evidence to the
>contrary.
>
That is indeed the most common measure. But there are other
measures. Most of the differences are restricted to the case
of the nonlinearity of s-boxes as opposed to individual functions.
I personally use the minimum hamming distance to the
set of affine functions. (Rueppel's critera). This is easy to
compute and relatively fast. Unless there is a reason to
use a more complicated implementation I generally stick
to that for computer programming.
The WHT is much better for algebraic analysis.
Did you receive the list of Citations that I sent you via e-mail?
>---
>Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
>Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
>
Mack
Remove njunk123 from name to reply by e-mail
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Tying Up Loose Ends - Correction
Date: Mon, 18 Sep 2000 01:39:22 GMT
On Sun, 17 Sep 2000 19:34:06 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>I don't think that it is worthwhile to worry about the
>slight 'increase in redundancy'.
My position is a bit different. I agree that it isn't so important as
to be *the* _sine qua non_ of good cryptography.
However, when known plaintext is not available, redundancy is what the
cryptanalyst has to grab on to. So the payoff from a reduction in
redundancy might be a significant reduction in the difficulty of the
ciphers the cryptanalyst can solve.
Thus, and because it's an interesting mathematical question as well, I
see no harm in investigating how the last little bit of redundancy can
be removed - and making use of such knowledge, once one has it
anyways, in encryption programs. Of course, more redundancy can be
removed by using a more detailed model of the plaintext (i.e.,
digraphic frequencies, instead of the single-letter frequencies I use
in examples) than by fiddling with the last few bits of the message.
The problem isn't making a little extra effort; the only real danger
is losing one's sense of perspective.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Tying Up Loose Ends - Correction
Date: Mon, 18 Sep 2000 01:34:08 GMT
On 17 Sep 2000 17:29:05 GMT, [EMAIL PROTECTED] (Guy Macon) wrote,
in part:
>Is there a particular reason why he couln't just state his position
>plainly
No, there isn't, and I'm annoyed with his behavior too. I'm not trying
to excuse him, but for information I am responding with what I have
gleaned of his argument from his several posts.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Tying Up Loose Ends - Correction
Date: Mon, 18 Sep 2000 01:42:29 GMT
On 17 Sep 2000 17:30:45 GMT, [EMAIL PROTECTED]
(SCOTT19U.ZIP_GUY) wrote, in part:
>Do you really belive quatom computers will not some day make mince meat of
>all the AES candidates in a few decades at most.
I can only honestly admit that I do not know.
Because that is at least a possibility (although some will argue that
this can't happen for 256-bit keys, only for 128-bit ones) I've been
trying to wrestle with designs that might fare somewhat better,
without being too far out.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: question about delastelle cipher in Bauer's book
Date: Mon, 18 Sep 2000 02:27:22 GMT
On Sun, 17 Sep 2000 22:41:56 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote, in part:
>Fritz Schneider wrote:
>> I'm working through F. L. Bauer's book "Decrypted Secrets" and ran
>> across something unfamiliar in section 4.2.3 (Delastelle cipher). He
>[snip]
>I looked at the place you referenced. The author's
>argument is indeed not clear and likely to be invalid.
Maybe it would have been clearer in the original German-language
edition.
But I think I can show that the author's argument _is_ valid, it just
wasn't spelled out in full.
The method of fractionation (also given in David Kahn's "The
Codebreakers" without this argument as an example of an amateur cipher
which is falsely seen as unbreakable) that involves shifting a message
by one place after the letters are converted to two numbers from 1 to
5 can indeed be attacked as if it is a homophonic cipher.
The "good" method of putting the digits from two letters in a square
by columns and taking them out by rows, by contrast, is a "true"
digraphic cipher, it is claimed.
The missing point is that it IS true that any digraphic cipher can be
thought of as a cipher with 26 homophones for the first letter, and
with 26 homophones for the second.
But in the former case, one has the same cipher with 26 homophones for
every letter - most importantly, for _consecutive_ letters. In the
"true" digraphic case, two _different_ homophonic ciphers alternate.
That is the key distinction, and it is the thing he failed to make
explicit - which is not necessarily a failing, since explaining
everything in detail would perhaps create problems of space.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Serpent S-boxes (again)
Date: Mon, 18 Sep 2000 03:11:59 GMT
On 18 Sep 2000 01:48:56 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (Mack) wrote:
>>On 17 Sep 2000 16:21:43 GMT, in
>><[EMAIL PROTECTED]>, in sci.crypt
>>[EMAIL PROTECTED] (Mack) wrote:
>>
>>>>[EMAIL PROTECTED] wrote:
>>>>: [EMAIL PROTECTED] (Gregory G Rose) wrote:
>>>>
>>>>:> I guess this could be considered an example of "proof by assertion",
>>>>:> but, has anyone actually checked the stated algorithm to see if it
>>>>:> does produce the chosen s-boxes?
>>>>
>>>>: The algorithm presented in the serpent paper is not complete they have
>>>>: a step labeled "test for given criteria" which doesn't say "how" the
>>>>: tests are done.
>>>>
>>>>*If* the criteria are well defined, it shouldn't matter how the tests are
>>>>done. For example, "non-linearity of 4" should be unambiguous, no matter
>>>>how you do your tests.
>>>
>>>In that specific case there are a number of measures of non-linearity.
>>>So it isn't really a well defined criteria.
>>
>>I basically dispute this. Yes, it is true that Boolean function
>>nonlinearity is applied to "bit-columns" in substitutions. This gives
>>a nonlinearity result for each column, which are then often combined
>>in some way. Typically we use either the minimum or the mean, and I
>>have used both.
>>
>>Developing two related results from exactly the same set of Boolean
>>function nonlinearity data hardly constitutes "a number of measures."
>>
>
>The idea of non-linearity is pretty straight forward but the specific
>phrase "a non-linearity of four" is ambiguous.
>
>Does it mean minimum maximum or mean. In this case I believe it is
>minimum distance to the set of affine functions.
I was probably extra inclusive to even mention the mean, perhaps
because I have actually used it. *Almost* universally the measure is
the minimum, not the mean. There is very little confusion in the
literature.
>It could also
>mean the sum of distances to affine funtions as has been used
>in the past.
I don't doubt the sum has been used somewhere. Clearly it is an
intermediate to computing the mean. As such, both carry essentially
the same meaning, and there is very little likelihood of confusing
such widely different values.
>>It is also true that "nonlinearity" originally implied a Fourier
>>transform of data. I speculate that this form in fact may be more
>>useful in the context of RNG's and stream ciphers.
>>
>>But for the past decade, s-box analysis has almost exclusively used
>>the Walsh-Hadamard transform (and correlation to the related "affine
>>Boolean functions" as opposed to sine waves of different frequency)
>>for Boolean function analysis.
>>
>>I would be most glad to receive any citations or evidence to the
>>contrary.
>>
>
>That is indeed the most common measure. But there are other
>measures.
I was looking for details on those "other measures." I mentioned both
the minimum and the mean of the set of Boolean function nonlinearity
results using the "affine Boolean function" basis. You mentioned the
sum; what else is there?
>Most of the differences are restricted to the case
>of the nonlinearity of s-boxes as opposed to individual functions.
>
>I personally use the minimum hamming distance to the
>set of affine functions. (Rueppel's critera).
But that *is* what the FWT computes. The FWT can be seen as just a
fast way to compute the differences to all the "affine Boolean
functions" simultaneously.
>This is easy to
>compute and relatively fast. Unless there is a reason to
>use a more complicated implementation I generally stick
>to that for computer programming.
>
>The WHT is much better for algebraic analysis.
I have no idea what distinction you are making.
>Did you receive the list of Citations that I sent you via e-mail?
Yes. You had two references not in my listings.
You are of course aware that I have multiple pages on this topic, with
long reference lists in each. These include:
http://www.io.com/~ritter/JAVASCRP/NONLMEAS.HTM
which is the JavaScript functioning article that not only describes
the background to the measure, but also does the nonlinearity
computation itself. It includes 23 references.
Another is:
http://www.io.com/~ritter/RES/SBOXDESN.HTM
which surveys 27 references in s-box design, including several on
nonlinearity.
These were done several years ago. Obviously I did not get
everything, and there should be more now. But I did get a lot.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Serpent S-boxes (again)
Date: Mon, 18 Sep 2000 03:14:04 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> [EMAIL PROTECTED] wrote:
> : [EMAIL PROTECTED] (Gregory G Rose) wrote:
>
> :> I guess this could be considered an example of "proof by
assertion",
> :> but, has anyone actually checked the stated algorithm to see if it
> :> does produce the chosen s-boxes?
>
> : The algorithm presented in the serpent paper is not complete they
have
> : a step labeled "test for given criteria" which doesn't say "how" the
> : tests are done.
>
> *If* the criteria are well defined, it shouldn't matter how the tests
are
> done. For example, "non-linearity of 4" should be unambiguous, no
matter
> how you do your tests.
Actually non-linearity of four is vague. It could mean an WT of 4, or
a distance of 4 from a linear function I suppose.
They would have been better served by giving the complete code for the
sbox maker.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: SDMI Crypto Challenge
Date: Mon, 18 Sep 2000 03:15:50 GMT
In article <8q386i$2ro$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Scott Craver) wrote:
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> >
> >If you can't hear the watermark then I can do an analogue rip. So
> >what. Or I can filter it out. Or ... Just like hiding messages in
> >JPEG's. I can always filter it out.
>
> None of these will work either. Any audio watermark worth
> the Barry Manilow it's printed on will be able to survive
> digital-analog conversion. Some survive FM transmission.
> And filtering is a brute process which will squelch the music
> along with the mark.
>
> You can, of course, remove a mark, if you know where it is
> and how it is embedded. Without that detail, it's not as
> easy.
If this black box mp3 codec knows where it is, then so will I. Nuff
said.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: One-way encryption
Date: Mon, 18 Sep 2000 03:17:42 GMT
In article <ed8x5.11268$[EMAIL PROTECTED]>,
"Thanh Diep" <[EMAIL PROTECTED]> wrote:
> Hi,
>
> I am looking for an one-way encryption algorithm to encrypt passwords
of
> about
> 20-character in length.
>
> I have been scanning various news group without much success. A few
> algorithms
> mentioned were: 3DES, MD5, SHA-1 and RIPE MD160, but I have no ideas
where
> to
> get them or how to implement.
>
> Ideally, I would like to have an algorithm to incorporate in my
system but
> will
> settle for a dll. My development platform is J++ on NT 4.0 and the
> application
> is running on the server side only. Please bear in mind that this is
a
> commercial application.
Hello clueless newbie. What's the name of your product? I want to
steer clear of it.
BTW I wouldn't really clump 3des and SHA in the same family of
algorithms.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Music Industry Offers US$10K for cracking their encryption system
Date: Mon, 18 Sep 2000 03:19:54 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED]
wrote:
> http://www.msnbc.com/news/460310.asp?cp1=1
>
congrats you have pointed out yet another stupid useless story in the
world. Considering what they want to solve is impossible I think the
story is very news worthy
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: A Degree in Encryption
Date: 18 Sep 2000 03:02:55 GMT
Mack <[EMAIL PROTECTED]> wrote:
> You have a pretty good choice of fields to get a degree in.
> Number Theory, Information Science, Information Theory ...
> But I don't know of a university that offers a degree program specifically
> in encryption.
They don't call it that on the degree; most places I know of would award a
degree in "Computer Science" or maybe "Math" or "Applied Math."
After all, cryptography is still just a subfield of all three of
those. Despite the amount of time we spend talking about it. :)
Even so, there *are* some universities you can attend with the intent of
getting a phd "in cryptography." These are the universities which host
professors who do research in crypto. You can go there and apply to do phd
research with these people. Bruce Schneier has an article "So
You Want To Be A Cryptographer" which has a little bit about this.
http://www.counterpane.com/crypto-gram-9910.html
The article defers the question of "which universities are good." David
Wagner asked that question a number of years ago and archived the answers
here:
http://www.cs.berkeley.edu/~daw/my-posts/phd-summary
If I had to give a similar table, it would look something like this. This
is mostly from memory, and I apologize for any errors or omissions (and
appreciate corrections). Ordering doesn't really matter, except that I
placed Harvard first as I'm attending there.
School Professors of Note
Harvard Rabin, Vadhan, Valiant
MIT Goldwasser, Micali, Rivest, Ohta(visiting)
UC Berkeley Wagner, Tygar, Trevisan(soon)
UWaterloo Menenzes, Van Oorschoot, Vanstone, Teske
UMontreal Brassard
McGill Crepeau
Columbia Yung, Syverson, Beaver(?), Stubblebine(??)
Stanford Boneh
CMU Rudich, Blum
Helsinki Tech Lipmaa
UC - Davis Rogaway
UC - San Diego Bellare, Miccancio, Yee
U Tokyo / NTT Okamoto, Ohta(permanent)
Princeton Sahai, Lipton, Arora
ETH Zurich Maurer, Damg*ard
KU Leuven Quisquater (also Guillou nearby), Rijmen, Preneel
Weizmann Goldreich, Shamir, Goldwasser(sometimes)
Technion Biham, Biryukov
U Georgia - Athens Pomerance and a number theory krewe
U Wisconsin Bach
NYU Rubin, Cranor, Dodis(maybe)
WPI Paar
Rochester Hemaspaandra, Ogihara (structural complexity)
Goethe U, Frankfurt Schnorr
Royal Holloway Davies, Shawe-Taylor
Cambridge Anderson, Merritt
UWashington Koblitz
CWI - Netherlands Don't know, but produced Chaum, Brands, and
Peter Montgomery
I would also look into where Andreas and Birgit Pfitzmann, Jacques Stern,
Michael Waidner, and some of the other people who worked on the CAFE and
SIRENE projects worked. These were early electronic commerce projects
in Europe which had some nice results.
You can get more info about many of these people by consulting a list of
cryptographers' home pages. Helger Lipmaa has one here:
http://www.tml.hut.fi/~helger/crypto/link/people/
his list of university sites is also worth looking at. David Wagner has
another list of cryptographers at
http://www.cs.berkeley.edu/~daw/people/crypto.html
Something I haven't mentioned up to now, but may be apparent from my
choice of cryptographers to mention above: there seem to be many different
"flavors" or "kinds" of cryptography.
A few of these flavors which I can distinguish:
* Some people like to investigate the connection between number theory and
cryptography (e.g. Koblitz, Menenzes), and spend time finding particular
constructions for use in cryptography and ways to implement them
efficiently. This approach is best exemplified in book form by Koblitz's
book on "Algebraic Aspects of Cryptography."
This "flavor" uses lots of number theory, deep algebaic results, and so
on. These are the people who enjoy finding new and better ways to do
primality tests, even after Rabin-Miller exists -- and they like to count
how many bad witnesses exist for numbers being tested. These people
will likely develop the next great factoring or discrete log algorithm.
* Some people like block ciphers. You can look at Knudsen's Block Cipher
Lounge for more information. http://www.ii.uib.no/~larsr/bc.html
See also Terry Ritter's pages at
http://www.io.com/~ritter/CRYPHTML.HTM
Tools here seem to include a massive amount of cleverness and acquaintance
with diverse results in combinatorics and statistics.
* Some people like stream ciphers. This is where you see things like
"siegenthaler's inequality" and "correlation-immune functions." Also shift
register sequences and some applications from theory of finite fields. I
don't know anything about this branch of cryptography.
* Some people like to investigate cryptography using concepts borrowed
from complexity theory. Goldreich's _Foundations of Cryptography
: Fragments of A Book_ at http://www.toc.lcs.mit.edu/~oded/frag.html
sets out this project in detail. These concepts include the notion of
explicit "definitions of security" against polynomial-time adversaries,
where "proofs of security" take the form of a reduction which shows that
if an adversary could "break" the cryptosystem, then it could violate
some plausible assumption (e.g. "factoring is hard.")
I say "using concepts borrowed from complexity theory" and not "based on
complexity theory" because, often as not, the assumption isn't explicitly
complexity theoretic in nature. That is, it's not "P != NP" but rather
"this function is too hard to invert." It's true that "this function is
hard to invert" implies "P != NP", but only for certain meanings of
"hard."
By the way, these reductions are also often "concrete" in nature. That is,
the amount of difficulty they "lose" can be precisely measured, so the
usual problem about NP-hardness results holding in the asymptote does not
apply. This is replaced with the wonderful new problem of estimating
the plausibility of the underlying assumption (e.g. what is the difficulty
of factoring?).
There is a separate investigation into such things as "well, can P != NP
imply a one way function?" and "do one way functions have complete
problems?" Not for faint of heart. :-\
This flavor also seems to branch out into lots of areas besides
encryption. See http://eprint.iacr.org/ for many examples.
* Some people like to investigate the "information theoretically
secure" cryptography, notably Maurer and Rabin. Similar definitions of
security as the previous flavor, but drop the "polynomial time" limit on
the adversary. By introducing other things, like a noisy channel, or
a space bound on the adversary, one can get other systems than the one
time pad. One can also get some nice MACs this way.
* Some people have logics for analyzing protocols. I don't know enough
about this type of cryptography, but it has some high-profile successes
(BAN logic, problems found in various protocols with automated analysis).
* Some people like to actually implement this stuff. and see what breaks.
or better yet, break it themselves. but that shades towards "computer
security" or "information security".
None of these are mutually exclusive, by the way. I am sure I've missed or
misinterpreted some major research thrust in crypto. which will hopefully
be pointed out to me.
My point in listing all this is that there are a LOT of different things
to do in this field. Answering your question "where should I go to study a
phd in cryptography?" will be much easier if you have some idea of what it
is you want to do. If you don't have such an idea, maybe because you don't
know what can be done, then you'll want to acquire some idea of what can
be done...which in turn will lead you to an idea of what you want to do.
why do you want to study for a phd in cryptography, anyway?
thanks,
-David Molnar
------------------------------
** 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
******************************
