Cryptography-Digest Digest #11, Volume #12 Mon, 12 Jun 00 16:13:01 EDT
Contents:
Re: Random sboxes... real info (tomstd)
Re: slfsr.c (Simon Johnson)
Card Shuffling Protocol (zapzing)
Card Shuffling Protocol (zapzing)
MDS and the Maximal Principle (tomstd)
Re: quantum cryptography at nytimes.com (Roger Schlafly)
Re: Double Encryption Illegal? (Simon Johnson)
Re: How does DES work? (Simon Johnson)
Re: How does DES work? (tomstd)
DER encoding ("Joseph Ashwood")
Re: How does DES work? ("Joseph Ashwood")
Re: DER encoding (Paul Rubin)
Re: How does DES work? (tomstd)
Matsui Style Sboxes (tomstd)
Re: Large S-Boxes (Mok-Kong Shen)
Re: FIPS-186 vs. FIPS-186-2 (Roger Schlafly)
----------------------------------------------------------------------------
Subject: Re: Random sboxes... real info
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 11:02:42 -0700
In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]>
wrote:
>[EMAIL PROTECTED] wrote:
>: tomstd <[EMAIL PROTECTED]> wrote:
>
>:> I.e is my point comming through? Random sboxes are hardly
ideal.
>
>: Ok Tom -- new assignment. Random S-boxes are bad. [...]
>
>Lots of folk like random s-boxes. To quote from BS's AC (p.
351):
>``my personal feeling is that S-boxes should be as large as
possible,
>random and key-dependent.''
>
>I don't usually number myself among lovers of large s-boxes -
but large
>random s-boxes aren't exactly bad. In fact they're usually
very good -
>and the bigger they are the better they are, in terms of
strength.
>
>Tom was closer to the mark - random s-boxes are rarely *ideal*.
>
>But what is an ideal s-box? The designers of DES had one idea -
we now
>know they were wrong.
>
>The "desirable" attributes of s-boxes are contradictory and
pull in
>different directions. The resulting boxes are always
compromises -
>emphasising one aspect at the expense of something else. The
very act of
>constraining s-boxes means the analyst has less potential
candidate
>s-boxes to consider if he attempts to consider all
possibilities for that
>component.
>
>At least large random s-boxes are unlikely to be systematically
weak.
>
>It's pretty hard to claim this about any constrained subset of
s-boxes,
>in the light of the possibility of unknown cryptanalytic
attacks from
>future analysts, or simply ones who do not publish their
results.
While I am going to retract abit of what I said...
Random sboxes *can* be partially ideal if they are constructed
properly. For example it's possible to construct a family of
sboxes by using a recursive design (like in Twofish) however it
has yet to be proven that the *entire* set of sboxes formed this
way are ideal.
I think random sboxes *can* be cryptographically suitable
provided they are constructed to be LP and DP bounded low enough
to avoid having them be super-weak. You can also design parts
of the cipher to cover for the sboxes. For example random 8x8
sboxes are very rarely LP/DP ideal or SAC/BIC ideal either.
However, if you have sufficient linear mixing after their usage
then SAC doesn't matter as much. This leads to weak keys
however where th sbox constructed is not within the DP/LP
bounds, and even through the linear step they are not
sufficiently ideal.
Another problem is non-bijectiveness. A construction of 8x32
sboxes to make a 32x32 sbox is rarely bijective which leads to
collisions in the output and free rounds in itterative attacks.
It's would be more ideal to use random bijective sboxes and
perform some linear step instead of making larger ones.
I.e you have to be careful.
The pros of ideal random sboxes is that statistical attacks
become much harder since the specific characteristics are rarely
known. This can make the construction much more secure.
My idea is to follow the Twofish idea and make sboxes along the
lines of
Sn+1 = S0 o S1 o S2 ... o Sn-1 o Sn
Where each 'S' is keyed, so for example, given five 8x8 sboxes
you can make a keyed 32-bit 8x8 sbox with
S5(x) = S0(S1(S2(S3(S4(x) ^ k3) ^ k2) ^ k1) ^ k0)
Then test all 2^32 possible sboxes for DP and LP maxes, and
SAC/BIC. Which leads to the suggestion of using fewer key bytes
to make the exhaustive test quicker. The amount of 'weak'
sboxes should be very very low to avoid them becomming a
hazard. If for example 2^16 of the sboxes are weak then the
cipher won't be very secure overall, but if only 2^8 are then it
would fair much better. The Sx() boxes should themselves have a
low DP/LP max as well as a non-linear order above one (i.e more
then simple BIC).
There is alot of merit in the idea of keyed substitution boxes,
however alot of care has to go into their construction. Large
random sboxes are rarely secure which is why they have to be
specifically constructed. For example look at a block 64-bit
cipher, only a handful of the 2^64! possible 64-bit
substitutions boxes are possible, but out of all of the possible
tables very few are weak. Try to think of the block cipher has
a big sbox and it will help you design smaller tables.
That's my two cents.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: slfsr.c
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 11:06:13 -0700
In article <[EMAIL PROTECTED]>, Simon
Johnson <[EMAIL PROTECTED]> wrote:
>I would have though having prime coeffients would make it
>irreducible & primitive, why does this not work Mod 2?
That's why :)
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Card Shuffling Protocol
Date: Mon, 12 Jun 2000 17:56:03 GMT
I believe I have come up with a card shuffling
protocol which may be interesting. I had to
come up with it as a part of my cryptographic
voting protocol. But since it could be useful on
its own I decided to post it separately.
Here's how it works: The players are arranged in
some order P0 ... Pnp-1. It does not matter which
player is first or last. Each player has a PGP-like
public and private key. I will call these "permanent"
keys even though they should probably be created
only for one deck shuffling and then destroyed
after that.
The cards are C0 ... Cnc-1. the cards are just
strings of bits, all of equal length.
P0 creates a large number of "decks". to create a deck
he Takes all the cards, appends a sufficiently
large random string to each card (different for
each card) and encrypts them using his permanent
private key. He then shuffles the cards in a random
order, that makes one deck.
A fair coin flipping protocol is used to decide on
which of P0's decks to use. P0 must then decrypt
all the other decks. This "cut and choose" procedure
insures that P0 has correctly followed the protocol.
P0 then passes the deck that is to be used to P1.
P1 "reshuffles" this deck by creating a large number
of reshuffled decks. A reshuffled deck is used by
taking the deck passed to P1 by P0, rearranging it
in a random order, appending a random string to
each card, and encrytping each card again in P1's
permanent private key.
Again, a fair coin flipping protocol is used to
decide which of these reshuffled decks to used,
and P1 must decrypt all the other decks.
this continues until all players have reshuffled
the deck.
The cards are dealt out according to whatever the
rules may be. If a player wants to know what
the value of his card is, he sends it to the
other players in reverse order to be blind-decrypted.
I believe this protocol will ensure that pllayers
all get the correct number of randomly selected
cards and no two cards will appear in any one deck.
Also a player can keep his card secret. When a player
chooses to reveal a card, everyone will know that it
was legitimately drawn by that player.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Card Shuffling Protocol
Date: Mon, 12 Jun 2000 18:02:17 GMT
I believe I have come up with a card shuffling
protocol which may be interesting. I had to
come up with it as a part of my cryptographic
voting protocol. But since it could be useful on
its own I decided to post it separately.
Here's how it works: The players are arranged in
some order P0 ... Pnp-1. It does not matter which
player is first or last. Each player has a PGP-like
public and private key. I will call these "permanent"
keys even though they should probably be created
only for one deck shuffling and then destroyed
after that.
The cards are C0 ... Cnc-1. the cards are just
strings of bits, all of equal length.
P0 creates a large number of "decks". to create a deck
he Takes all the cards, appends a sufficiently
large random string to each card (different for
each card) and encrypts them using his permanent
private key. He then shuffles the cards in a random
order, that makes one deck.
A fair coin flipping protocol is used to decide on
which of P0's decks to use. P0 must then decrypt
all the other decks. This "cut and choose" procedure
insures that P0 has correctly followed the protocol.
P0 then passes the deck that is to be used to P1.
P1 "reshuffles" this deck by creating a large number
of reshuffled decks. A reshuffled deck is used by
taking the deck passed to P1 by P0, rearranging it
in a random order, appending a random string to
each card, and encrytping each card again in P1's
permanent private key.
Again, a fair coin flipping protocol is used to
decide which of these reshuffled decks to used,
and P1 must decrypt all the other decks.
this continues until all players have reshuffled
the deck.
The cards are dealt out according to whatever the
rules may be. If a player wants to know what
the value of his card is, he sends it to the
other players in reverse order to be blind-decrypted.
I believe this protocol will ensure that pllayers
all get the correct number of randomly selected
cards and no two cards will appear in any one deck.
Also a player can keep his card secret. When a player
chooses to reveal a card, everyone will know that it
was legitimately drawn by that player.
--
If you know about a retail source of
inexpensive DES chips, please let
me know, thanks.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: MDS and the Maximal Principle
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 11:12:37 -0700
Are MDS matrcies and the "Maximal Principle" related in any
way? It's sound like they are.
According to my linear alg book I am reading I have
"Let F be a family of sets. If for each chain G [ F there
exists a member of F that contains each member of G, then F
contains a maximal element"
Where '[' is the right facing sideways U (underline), which I
think means "a subset of".
I am really not versed in linear alg, which is why I am trying
to read this book. Anyways the ideas look related...
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: quantum cryptography at nytimes.com
Date: Mon, 12 Jun 2000 10:35:39 -0700
> See http://www.nytimes.com/library/magazine/home/20000611mag-code.html
IMO, the usual bogus hype.
Unprecedented secrecy and security -- two commodities that are
increasingly rare in a world dominated by the free flow of
information.
For futurists, the development of quantum cryptography is a kind of
cosmic victory for personal privacy.
Quantum crypto is never going to doing anything for personal privacy.
The beauty of the system is that two branches of a bank, say, do not
actually have to send the record of a transaction itself. The two
branches
simply work up a long string of random numbers known only to them,
using the faint laser pulses. Those numbers act as a code to encrypt
the
digital version of a transaction. The encrypted version can be sent
over
just about any sort of communication line.
So they want to use quantum crypto to generate a random key,
and then use it as a pure OTP. Dumb idea, and it will never
happen. Banks would be better of sticking with (single) DES.
------------------------------
Subject: Re: Double Encryption Illegal?
From: Simon Johnson <[EMAIL PROTECTED]>
Crossposted-To: comp.databases.oracle
Date: Mon, 12 Jun 2000 11:20:59 -0700
Its one of these useless laws. Even if you do use multiple
passes of an algorithm with independent keys and they *tried* to
convict you, they would be stuffed.
They can't *prove* you used the algorithm on a piece of data
twice without brute-forcing double the key-space of the
encrypting algorithm.
Like i said - Pointless
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: How does DES work?
From: Simon Johnson <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 11:34:02 -0700
> DES is certainly a dead cipher, but you can find some papers
Eli
> Biham on DES (he is one of the dudes that broke DES). Also
> check out FIPS-42 I think... (NIST).
> Tom
Its not dead, but it should be. Even the slightest weakness
should be reason enough to stop using a cipher. Besides, there
are much faster and to be frank, much better, ciphers out there.
Though for an introduction to block ciphers, DES is probably
unbeatable.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Re: How does DES work?
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 11:41:03 -0700
In article <[EMAIL PROTECTED]>, Simon
Johnson <[EMAIL PROTECTED]> wrote:
>
>> DES is certainly a dead cipher, but you can find some papers
>Eli
>> Biham on DES (he is one of the dudes that broke DES). Also
>> check out FIPS-42 I think... (NIST).
>
>> Tom
>
>Its not dead, but it should be. Even the slightest weakness
>should be reason enough to stop using a cipher. Besides, there
>are much faster and to be frank, much better, ciphers out there.
>
>Though for an introduction to block ciphers, DES is probably
>unbeatable.
DES is a good starting ground for Cryptanalysis, but not cipher
design. There are a plethora (I like that word) of papers on
the cryptanalysis of DES that are ideal to learn from.
Espescially Bihams' papers on Diff and Matsui's Linear attacks.
He has done a wonderful service to the community by providing
those papers.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: DER encoding
Date: Mon, 12 Jun 2000 11:44:58 -0700
I just figured I'd pop my head up and ask a question that I know has an
answer. I'm looking for a (hopefully free) code generator for DER encoding,
specifically for PK-INIT (kerberos) right now, but later for other things as
well. Does anyone have any ideas of where I'd find one that's at least
useful, I'm tired of writing the code.
Joe
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: How does DES work?
Date: Mon, 12 Jun 2000 11:49:17 -0700
> Even the slightest weakness
> should be reason enough to stop using a cipher.
But we have no perfect ciphers. Every AES finalist has been shown to have
extremely minor weaknesses against something, and to be based on assumptions
that we cannot prove. I think we can agree that those 5 are the best of the
best right now. I find it encouraging that the attacks are so close to the
difficulty of a brute force search.
Joe
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: DER encoding
Date: 12 Jun 2000 19:04:00 GMT
In article <uIqqP5J1$GA.329@cpmsnbbsa07>,
Joseph Ashwood <[EMAIL PROTECTED]> wrote:
>I just figured I'd pop my head up and ask a question that I know has an
>answer. I'm looking for a (hopefully free) code generator for DER encoding,
>specifically for PK-INIT (kerberos) right now, but later for other things as
>well. Does anyone have any ideas of where I'd find one that's at least
>useful, I'm tired of writing the code.
There is stuff for this in the OpenSSL package, www.openssl.org.
------------------------------
Subject: Re: How does DES work?
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 12:06:55 -0700
In article <eZcxp7J1$GA.325@cpmsnbbsa07>, "Joseph Ashwood"
<[EMAIL PROTECTED]> wrote:
>> Even the slightest weakness
>> should be reason enough to stop using a cipher.
>But we have no perfect ciphers. Every AES finalist has been
shown to have
>extremely minor weaknesses against something, and to be based
on assumptions
>that we cannot prove. I think we can agree that those 5 are the
best of the
>best right now. I find it encouraging that the attacks are so
close to the
>difficulty of a brute force search.
Now don't be hypocritical my friend. The best attack on DES is
about as close to the bruteforce as well (well off by 2^13).
I don't want to put words in your mouth, but by your previously
expressed logic if a AES cipher can be broken by say 2^243 work
then it would be weak as well?
To be fair, i find it comforting that none of the AES finalists
have been broken by conventional means of attack too.
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
Subject: Matsui Style Sboxes
From: tomstd <[EMAIL PROTECTED]>
Date: Mon, 12 Jun 2000 12:17:33 -0700
What about using sboxes of the same stye in GF(p^n) where p != 2?
For example using multiplicative inversion in GF(4^2) would get
you a 8x8 sbox. I will try to modify some exisiting code todo
this...
any insight though?
Tom
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Large S-Boxes
Date: Mon, 12 Jun 2000 21:43:23 +0200
lordcow77 wrote:
> I can't help but to question what exactly it is you are
> attempting to accomplish.
Well, to learn more about cryptology, also with the assumption that
I am not the single one in the group that wants to learn something.
M. K. Shen
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: FIPS-186 vs. FIPS-186-2
Date: Mon, 12 Jun 2000 11:50:56 -0700
Martin Hamann wrote:
> What are the differences in the FIPS-186 (1994) and the FIPS-186-2 (2000)
> standards. Both are issued by NIST and defines the Digital Signature
> Algorithm. I guess the standard has just been updated, but does anyone know
> what the differences are ?
The newer one allows use of RSA and ECDSA, as well as DSA.
But the use of RSA and ECDSA must conform to ANSI banking
standards. Those standards have peculiarities, such as
requiring RSA primes to be pseudo-random, rather than
random.
------------------------------
** 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
******************************
