Cryptography-Digest Digest #891, Volume #12 Tue, 10 Oct 00 19:13:01 EDT
Contents:
Thank you ("William A. McKee")
A general substitution scheme with variable-length codes (Mok-Kong Shen)
Re: SSL/TLS Certificate Request message ("Nelson B. Bolyard (At Home)")
Re: RC6 royalty free or not? (Andru Luvisi)
pass phrases and key generation (and Kerberos) (Ken Raeburn)
Re: Dense feedback polynomials for LFSR (zapzing)
Re: How Colossus helped crack Hitler's codes (John)
Re: A new paper claiming P=NP (Bill Unruh)
Re: Comments on the AES winner (Future Beacon)
Re: My view of election. (Roger Schlafly)
Re: Dense feedback polynomials for LFSR ("bubba")
Re: Storing an Integer on a stream ("Matt Timmermans")
Re: Deadline for AES... ("Douglas A. Gwyn")
Re: Microsoft CAPI's PRNG seeding mechanism (Tim Tyler)
Re: Microsoft CAPI's PRNG seeding mechanism (Tim Tyler)
----------------------------------------------------------------------------
Reply-To: "William A. McKee" <[EMAIL PROTECTED]>
From: "William A. McKee" <[EMAIL PROTECTED]>
Subject: Thank you
Date: Tue, 10 Oct 2000 19:14:52 GMT
Thank you to everyone who contributed to my threads.
My project is well in hand thanks to you guys.
Cheers,
Will McKee.
--
William A. McKee
[EMAIL PROTECTED]
Asia Communications Quebec Inc.
http://www.cjkware.com
"We're starfleet: weirdness is part of the job." - Janeway
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: A general substitution scheme with variable-length codes
Date: Tue, 10 Oct 2000 21:30:44 +0200
Abstract. It is shown how to use a pair of arbitrary
Hoffman codes to encrypt given bit sequences.
A substitution in modern crypto algorithms is commonly a
mapping of n bit values to m bit values, with both n and
m being constant. A typical example is the DES S-boxes
with n=6 and m=4. That is, the input and output symbols are
both from constant length codes (block codes). Evidently,
however, there is no 'necessity' of using such constant
length codes. Thus we describe in the present note a more
general substitution from an input alphabet to an output
alphabet, where the symbols of the alphabets have variable
number of bits as code values. Given an arbitrary bit
sequence, the substitution process then consists in
identifying (pattern matching) successive groups of bits
that represent valid symbols in the input alphabet and
replacing these with corresponding groups of bits in the
output alphabet according to a mapping that in general may
be one-to-many (homophones).
We shall concern ourselves in the following only with
substitutions that are reversible. For that purpose the
prefix property of the codes is evidently required. Thus
the Huffman procedure of constructing codes suggests itself.
Since our goal here is not compression but only to obtain
arbitrary variable length codes, we don't consider any
frequency distributions in the construction. As will be
detailed below, we employ in fact entirely arbitrary
(random) Huffman trees.
To construct a code for an alphabet of s symbols, i.e.
to determine their code values (bit representations), we
proceed as follows:
Use a PRNG (with a secret seed) to generate a (pseudo-)
random regular binary tree having s terminal nodes. (A
binary tree is regular, if each non-terminal node has
exactly two branches.) Label the two branches issuing from
any internal node with 0 and 1 in the manner familiar with
Huffman trees. Apply any chosen method of traversal of
the tree to obtain from the set of terminal nodes the
desired sequence of s code values. We shall refer to this
sequence (array) in the following as the input (resp.
output) symbol set (of an input (resp. output) alphabet).
Our substitution to be done on a given bit sequence is then
performed according to an arbitrary invertible (in general
one to many, not necessarily surjective) mapping of the
symbol set of an alphabet of size u to the symbol set of
another alphabet of size v, both being randomly constructed
as above, with the constraint 2 <= u < v. It should be
remarked that for the purpose of the present note the
values u and v can be arbitrarily chosen by the user. They
need to have nothing to do at all with the size of the
English alphabet or the size of the ASCII character set,
even in case the given bit sequence is indeed the ASCII
representation of an English text.
In order to ensure that any arbitrary input bit sequence
can be transformed into an output bit sequence with a pair
of alphabets described above and be able to be subsequently
transformed back exactly, it is necessary to deal with the
case where the last group of bits of the input bit sequence
fails to correspond to any element of the input symbol set.
For that purpose we require that there be one (or more)
element of the output symbol set which is not mapped to
by any element of the input symbol set (that's why u < v
in the above is necessary) and which we designate as EOF.
Since the Huffman trees are regular, the last group
of bits of the input bit sequence must either exactly
correspond to an element of the input symbol set or else
form the (proper) prefix of one or several of such elements
(in which case we arbitrarily choose one of these). Thus
this group of input bits can always be determined via the
said element of the input symbol set and a binary number
giving the length of the prefix concerned. On the output
stream we first emit the corresponding element of the
output symbol set, to be followed by the EOF (choose anyone
if there are several) and then the above said length. (The
length field must be able to contain the maximum length of
the code values of the input alphabet). Thereafter we
output, if necessary, random bits to fill to any boundary
(byte/word/block/record) that is desired for the output
bit sequence. It is clear that with the above procedure
the given input bit sequence can always be faithfully
recovered from our output bit sequence.
We can apply multiple passes of such substitutions on a
given bit sequence, employing for different passes different
pairs of alphabets (with in general different values of
u and v). Due to the fact that the codes are of varaible
length, two passes cannot in general be equivalent (i.e.
be reduced) to a single pass, which means that we can in
fact increase the 'complexity' for the oppnent through
superencipherment. Contrast this with successive
application of two monoalphabetical substitutions in the
classical sense, which are always equivalent to one single
monoalphabetical substitution.
Instead of using a single pair of alphabets (in one pass),
we can also employ a number of pairs of alphabets (with in
general different values of u and v) to perform a
'polyalphabetical substitution', using e.g. a PRNG to
dynamically select the alphabet pairs as the encryption
process goes on.
Note that an interesting special case is one where u=2,
while v is chosen arbitrarily large so as to have
substantial number of homophones and further the mapping
is also largely non-surjective such that quite a number
of different dummy output symbols are available for
arbitrary insertion into the output stream to confound
the opponent.
Finally we note that the basic idea of using random Huffman
trees (i.e. independent of any frequency considerations)
for encryption goes back in my knowledge to S. Hallyn, who
restricted however one member of the alphabet pair, namely
the input alphabet, always to be a block code, e.g. ASCII,
and considered always bijective mappings of the symbol sets.
The generalization given above is more versatile and hence
may be more advantageously employed to resist analysis.
M. K. Shen
============================
http://home.t-online.de/home/mok-kong.shen
------------------------------
From: "Nelson B. Bolyard (At Home)" <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Crossposted-To: alt.security
Subject: Re: SSL/TLS Certificate Request message
Date: Tue, 10 Oct 2000 19:39:56 GMT
Johnny wrote:
>
> Hello!
> I am implementing SSL protocol and have problems with server's Certificate
> Request.
> Does anybody know what should be the format of Distinguished Name within the
> above
> message? Is it ASN.1/BER encoded DN like within X.509 certificate or simple
> plaintext
> cn=..., o=..., c=.. Maybe it is something else. Or does MSIE not understand
> this
> message, because it disconnect upon receiving this message?
>
> Thanks in advance.
> Marcin
It is an ASN.1/DER encoded DN.
There's a newsgroup dedicated to SSL development questions.
This link will take you there:
snews://secnews.netscape.com/netscape.dev.ssl
/Nelson
------------------------------
From: Andru Luvisi <[EMAIL PROTECTED]>
Subject: Re: RC6 royalty free or not?
Date: 10 Oct 2000 12:40:04 -0700
[EMAIL PROTECTED] (Sami J. M�kinen) writes:
[snip]
> I couldn't tell by reading the papers from RSA webpage that
> is RC6 royalty free or not (to use in shareware program)?
>
> I'm talking about the algorithm itself, not any implementation.
[snip]
I emailed RSA Security back when this thread started and asked them.
I got a response today saying about what we would expect: Patent
pending, all rights reserved, get a copy of BSAFE if you want to use
it. Cheap educational use only licenses are available to students.
Andru
--
Andru Luvisi, Programmer/Analyst
------------------------------
Subject: pass phrases and key generation (and Kerberos)
From: Ken Raeburn <[EMAIL PROTECTED]>
Date: 10 Oct 2000 16:23:01 -0400
I'm looking at putting together a spec for using Rijndael and/or
Twofish in Kerberos. Mostly it looks straightforward, my main concern
is with key generation from pass phrases. (Though if anyone wants to
comment on the key derivation scheme I'm thinking of using, described
in http://www.mit.edu/~marc/krb-3des/key-derivation-03 and
http://www.mit.edu/~marc/krb-3des/kerb-key-derivation-01, I'm happy to
listen; AFAICT it's okay as is.)
What schemes are preferred for (deterministically) generating keys
from pass phrases?
The algorithms we're using so far are all based purely on the
encryption algorithms the key will be used with, not on hashing
algorithms. I think the reasons are mostly historical, but I'd just
as soon not break with the pattern without good reason.
Does a CBC-MAC, using a key and initial vector either predefined and
public or derived from the input string, do good mixing and entropy
preservation? One of the algorithms we're using now does a DES
CBC-MAC over the input string (pass phrase plus a salt), but uses a
XOR'ed fan-folding of the string as both the key and ivec; I've heard
that may weaken it somewhat.
The other algorithms we're using now use n-fold (described in
Blumenthal, U., "A Better Key Schedule for DES-Like Ciphers",
Proceedings of PRAGOCRYPT '96, 1996) on the string, but n-fold looks
lousy at preserving entropy in certain cases to me, and that doesn't
appear to be what it was originally intended for. One then feeds it
to the triple-DES key derivation routine (uses input to encrypt a
known constant, and if more output key bits are needed, re-encrypts
the first output block to get the second, etc). The other also uses
n-fold, and encrypts the n-fold result a couple times using the n-fold
result as the key. Since the only input to the encryption in both
cases is the n-fold output, I think we could do better.
Should I give up on encryption-based schemes and just go with SHA1 (or
SHA2 eventually)?
Ken
------------------------------
From: zapzing <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Date: Tue, 10 Oct 2000 20:53:10 GMT
In article <Vu6E5.32$[EMAIL PROTECTED]>,
"bubba" <[EMAIL PROTECTED]> wrote:
> Yes, choose your length, say 100 bits and a dense starting point,
> say 0x1ABCDEF1234567890ABCDEF012. To find the next
> 100 primitive polynomials, use:
>
> ppsearch128 bits=100 hex poly=0x1ABCDEF1234567890ABCDEF012 search=100
>
> (from
http://sduplichan.home.att.net/primitive/primitivePolynomials.htm)
>
Incredible explanation! I actually understood it!
I was just reading Bruce S's book "Applied
Cryptography" and wondering to myself why he
recommends using dense polynomials, but only
gives examples of sparse polynomials. Perhaps
he's working for the NSA ?
On another note, it seems to me that making the
polynomial itself a part of the key would
greatly increase security, but that possibility
is barely mentioned in his book.
Do you have any info on that?
--
Void where prohibited by law.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: John <[EMAIL PROTECTED]>
Subject: Re: How Colossus helped crack Hitler's codes
Date: Tue, 10 Oct 2000 22:06:33 +0100
In article <[EMAIL PROTECTED]>, Andrew
McDonald <[EMAIL PROTECTED]> writes
>On Mon, 02 Oct 2000 21:50:33 +0200,
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>
>> My memory isn't too well about I lecture that I heard
>> several years ago. The lecturer, if not director, had
>> at least a rather important position in the museum.
>> I have now not the faintest idea of his name. He said
>> that he was writing a book about the machine and the
>> crypto techniques involved. He seemed to have been
>> principally involved in the reconstruction of the machine.
>
>That would probably be Tony Sale then. Looking on amazon.co.uk, there
>appears to be a book titled "The Colossus Computer 1943-1996" by him.
It would indeed.
You can find a lot of information about BP on their web site;
http://www.bletchleypark.org.uk/
If you are interested in the maths (or math if your in the USA) of
Colossus then follow the mail order link. There is a small report by
Tony Sale called something like "Code breaking with Colossus" that costs
about GBP2.50 There are many other books and publications also.
--
John Cameron.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 10 Oct 2000 21:24:34 GMT
In <[EMAIL PROTECTED]> Dima Pasechnik <[EMAIL PROTECTED]> writes:
>Stas Busygin <[EMAIL PROTECTED]> writes:
>> Paul Rubin wrote:
>> >
>> > Any chance of providing a pdf file? The .ps.zip and .ps.gz files are
>> > hard to view in a browser.
>> Sorry, not just now. I have a limited space on the web server.
Just download the ps file and then use ps2pdf to change it to a pdf
file.
------------------------------
From: Future Beacon <[EMAIL PROTECTED]>
Subject: Re: Comments on the AES winner
Date: Tue, 10 Oct 2000 17:55:03 -0400
On Mon, 2 Oct 2000, Mok-Kong Shen wrote:
>
>
> Anton Stiglic wrote:
> >
> > In a rump session talk at Crypto 2000, N. Ferguson
> > (I believe it was) came up with an equation, in GF(2^8)
> > I believe, stating that if one can solve this equation
> > one can break Rijndael encryption. I taught it was a
> > very nice abstraction.
> > I did not note down the equation (the cipher I know
> > the less is in fact Rijndael, but I guess this is going
> > to have to change now... :).
> >
> > Someone knows what the equation was?
>
> I don't know but I think that the fact that Rijndael
> has only one S-box should be discussed concerning its
> advantages/disadvantages.
>
> M. K. Shen
Does anybody think that the United States Government cannot crack
this code?
Jim Trek
Future Beacon Technology
http://eznet.net/~progress
[EMAIL PROTECTED]
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: My view of election.
Date: Tue, 10 Oct 2000 14:57:48 -0700
"SCOTT19U.ZIP_GUY" wrote:
> I feel Gore will do more to keep crypto closed then Bush.
Certainly that has been Gore's record.
"A zebra does not change it's spots."
-- Al Gore, attacking President George Bush in 1992
------------------------------
From: "bubba" <[EMAIL PROTECTED]>
Subject: Re: Dense feedback polynomials for LFSR
Date: Tue, 10 Oct 2000 22:16:05 GMT
"zapzing" <[EMAIL PROTECTED]> wrote in message
news:8rvvji$p13$[EMAIL PROTECTED]...
> In article <Vu6E5.32$[EMAIL PROTECTED]>,
> "bubba" <[EMAIL PROTECTED]> wrote:
> > Yes, choose your length, say 100 bits and a dense starting point,
> > say 0x1ABCDEF1234567890ABCDEF012. To find the next
> > 100 primitive polynomials, use:
> >
> > ppsearch128 bits=100 hex poly=0x1ABCDEF1234567890ABCDEF012 search=100
> >
> > (from
> http://sduplichan.home.att.net/primitive/primitivePolynomials.htm)
> >
>
> Incredible explanation! I actually understood it!
> I was just reading Bruce S's book "Applied
> Cryptography" and wondering to myself why he
> recommends using dense polynomials, but only
> gives examples of sparse polynomials. Perhaps
> he's working for the NSA ?
>
> On another note, it seems to me that making the
> polynomial itself a part of the key would
> greatly increase security, but that possibility
> is barely mentioned in his book.
> Do you have any info on that?
Maybe someone else can answer this one. I am very new to
crypto, the LFSR familarity comes from encountering them
in other applications.
>
> --
> Void where prohibited by law.
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Storing an Integer on a stream
Date: Tue, 10 Oct 2000 17:42:30 -0400
Reply-To: "Matt Timmermans" <[EMAIL PROTECTED]>
If I can assume that what you're really doing is breaking a file into N bit
blocks for encryption, then it is best not to write the length at all. It's
mostly the same as the length of the output file, and so it's mostly known
plaintext.
The simplest thing to do is just write a small integer X at the end of the
last block, where X is the number of random pad bytes that should be
discarded. Note that you may have to add a whole new block just to hold X.
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> If I'm writing a file, whose format is a 64 bit file length, followed by
> some amount of data, followed by some [random] padding, which of the
> following is the best way to store that length value:
>
> 1) 8 base-256 digits. With this format, we always use 8 bytes.
> 2) Some number of base-255 digits, with leading 0 digits stripped,
> terminated by the value 255. With this format, we always use at least 1
> byte (for a value of 0, which is written as just the terminator (255)),
> but generally use 2..9 bytes.
> 3) Some number of base-128 digits, with leading 0 digits stripped, all
> but the last prefixed by a 0 bit, and the last prefixed by a 1 bit.
> With this format, values 0..127 use 1 byte, 128..(128**2-1) uses 2
> bytes, etc, with 9 bytes being used for a 63 bit value, and 10 bytes
> used for a 64 bit value.
>
> Since this file will be encrypted, any file lengths that are
> significantly less than 2**64, which is most files, will give some known
> plaintext of leading 0s with method 1. I made a suggestion of using
> method 3, to avoid this problem, but someone (I forget who) said that
> method 2 was more space efficient. Does anyone have any comments? Both
> on space-efficiency and on difficulty of using it for trial decryptions.
>
> By the way, I think I should mention that in the perl programming
> language, the builtin functions pack() and unpack() have a template type
> for method 2, which (If I recall correctly) uses the letter 'w' and is
> refered to as Berweiss-encoding of an integer.
>
> --
> ... perfection has been reached not when there is nothing left to
> add, but when there is nothing left to take away. (from RFC 1925)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Deadline for AES...
Date: Tue, 10 Oct 2000 21:39:18 GMT
Mok-Kong Shen wrote:
> My point is that the user should be able to verify that
> the chosen s-box indeed is the optimum (or one among
> 'equally' optimals ones) satisfying the above criteria.
Why? Do you need to similarly validate the choice of
blue paint vs. red on the head cover of an automobile engine?
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Microsoft CAPI's PRNG seeding mechanism
Reply-To: [EMAIL PROTECTED]
Date: Tue, 10 Oct 2000 22:14:04 GMT
In sci.crypt.random-numbers [EMAIL PROTECTED] wrote:
: All this debate on the "security" of M$'s CAPI does still not answer
: the question how the Api CryptGenRandom seeds random data.
http://msdn.microsoft.com/library/psdk/crypto/cryptoref1_15t9.htm
...suggests you have to seed it yourself:
``If an application has access to a good random source, it can fill the
pbBuffer buffer with some random data before calling CryptGenRandom. The
CSP then uses this data to further randomize its internal seed. It is
acceptable to omit the step of initialize the pbBuffer buffer before
calling CryptGenRandom.''
It doesn't say exactly what happens if you don't supply some random data.
In fact it doesn't even say if the underlying construct is a PRNG, or
something like Yarrow - let alone provide source for it ;-(
: I guess some reverse engineering is required here, if there is no
: further info from M$ itself.
For more information consider contacting the supplier - reverse
engineering may put you in breach of the license conditions.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
Crossposted-To: sci.crypt.random-numbers
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Microsoft CAPI's PRNG seeding mechanism
Reply-To: [EMAIL PROTECTED]
Date: Tue, 10 Oct 2000 22:43:11 GMT
In sci.crypt.random-numbers Pascal JUNOD <[EMAIL PROTECTED]> wrote:
: By the way, the seeding mechanism source of sun.security.* Java package
: is not available, or am I wrong ?
Apparently, it's in the SecureRandom documentation:
``Note however, that our seed generation algorithm has not been thoroughly
studied or widely deployed. It relies on counting the number of times
that the calling thread can yield while waiting for another thread to
sleep for a specified period.''
The algorithm is notoriously slow.
Different providers can specify their own seeding mechanism within the
SecureRandom framework, if they so choose.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
** 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
******************************
