Cryptography-Digest Digest #953, Volume #12 Wed, 18 Oct 00 16:13:01 EDT
Contents:
Re: FTL Computation (ca314159)
Re: CHAP security hole question ([EMAIL PROTECTED])
Re: Rijndael in Perl (Dido Sevilla)
Re: Looking for paper (Benjamin Goldberg)
Re: Huffman stream cipher. (Mok-Kong Shen)
Re: Rijndael implementations (Benjamin Goldberg)
Re: Enigma: Stolen German Code Machine Turns Up in BBC Mailroom (James Felling)
Re: Looking for small implementation of an asymmetric encryption (Jon Walker)
Re: algo to generate permutations ([EMAIL PROTECTED])
Re: ---- As I study Rinjdael... (James Felling)
Re: Looking for small implementation of an asymmetric encryption algorithm
([EMAIL PROTECTED])
Re: working with huge numbers (Ray Dillinger)
----------------------------------------------------------------------------
From: ca314159 <[EMAIL PROTECTED]>
Crossposted-To: sci.astro,sci.physics.relativity,sci.math
Subject: Re: FTL Computation
Date: Wed, 18 Oct 2000 19:05:01 GMT
In article <9OjH5.61945$[EMAIL PROTECTED]>,
"Paul Lutus" <[EMAIL PROTECTED]> wrote:
> [ snip unbelievable trash ]
ditto
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: CHAP security hole question
Date: Wed, 18 Oct 2000 19:13:38 GMT
Thank you very much for your reply. Please see my questions following
your cooments.
In article <8skfb2$6gv$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Vernon Schryver) wrote:
> MS does not have an implementation of CHAP, but a protocol that is
> distinct from CHAP defined in RFC 1994. A good comparison between
> MS-CHAP and the RFC 1994 standard can be found starting on page 113 of
> "PPP Design, Implementation, and Debugging," second edition, by James
> Carlson. Even people who are very familiar with PPP can find useful
> information in Carlson's book on the PPP protocols not documented or
> not fully documented in any RFC.
What are other authentication and key-exchange protocols besides CHAP?
It seems to me that CHAP originated from PPP. I am trying to search
for all authentication and key-exchange protocols so that I can compare
which one can better suit my need. BTW, my need is, first, to
authenticate a user, second, to prevent socket connections from
unauthenciated user.
>
> Carlson lists three main holes in MS-CHAP. The first is not really
> a hole in MS-CHAP but the observation that it is posible to obtain
> lists of passwords from Microsoft systems. Anything based on shared
> secrets is no stronger than the secrecy of those secrets.
Does this mean that a general weakness of CHAP is its sharing of secret
keys between a server and all its clients?
>
> The second is that Microsoft uses a single secret to authenticate both
> a source of PPP packets and access to a user account. The ability to
> send PPP packets to a system is generally no worse than what can be
done
> to the same system through its other network connections by any random
> bad guy without any secret knowledge, while access to an account is
the
> whole thing. Other brands of systems can distinguish the two. If a
bad
> guy gets a CHAP secret, all that need be compromised is IP packet
access,
> but an MS-CHAP secret is often useful for more serious dirty work.
>
You said "other brands of systems can distinguish the two". Can you
name some of these "other systems"?
Aagain, thank you for your info.
c6ap
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Crossposted-To: comp.lang.perl.misc
Subject: Re: Rijndael in Perl
Date: Thu, 19 Oct 2000 03:13:44 +0800
"Tony L. Svanstrom" wrote:
>
> Anyone that knows if Rijndael exists in Perl yet and/or if someone's
> working on it?
>
Well, I've been working on a Crypt-CBC-compatible module that uses
Rijndael, but I'm learning how to program Perl modules while I'm at it,
so progress is somewhat slow. It uses (er...will use) my own Rijndael C
implementation, which is somewhat less flexible than the original fast C
versions available from the Rijndael website (only thing it doesn't
support yet is variable block sizes), but is definitely licensed under
either LGPL or Artistic License, as opposed to the somewhat questionable
licensing for the original Rijndael reference specs available on the
website i.e. there is no word on that on the website or auxiliary files
in the tarball, so we must assume that these implementations are not
freely usable except as reference code.
If anyone wishes to help me a little here, drop me a line.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Looking for paper
Date: Wed, 18 Oct 2000 19:23:53 GMT
Joseph Ashwood wrote:
>
> [snip]
> > Assuming that at each step, the order of the A-Zs used
> > for the branches is randomly shuffled.
> Right there you've done 2 things, you've changed the problem (from
> static tree to non-static tree), and by the way you've stated it
> you've made it equiavalent to a OTP (each permutation is equally
> likely, therefore it is a OTP). Now there will be flaws in the way you
> implement your "random" shuffle, and that will be the basis of the
> attack. My statement was on the static tree idea, and that is a
> mono-substitution.
You have quite clearly misinterpreted my description. When I said "at
each step," I meant each step of constructing the tree. This is
equivalent of having a regular huffman tree, and for each branch,
swapping (or not swapping) at random, based on the output of a TRBG.
> > So instead of a mono-alphabetic
> > substitution, we have a mono-dictionary substitution.
>
> You've already changed your stand. First it was a random shuffle, now
> it's a choice of relatively optimal compression substitutions.
No. First, when it was bits&letters it was random labeling of branches
(labeling 0 and 1 versus 1 and 0 is the same as swapping (or not
swapping) the children of a node. After changing to letters&words, it
was random labeling of branches (but there are 26 children of each node,
so I shuffle the letters A-Z and use them as labels).
> The difference is substantial, one qualifies as a OTP, the other is a
> poly-alphabetic substitution,
No and no. A huffman tree of bits mapping to letters is in NOT a
poly-alphabetic substitution. If you take two polyalphabetic
substitutions, your ciphertext is equivalent to enciphering your
plaintext under a single other polyalphabetic substitution. That is to
say, for all substitutions k1, k2, there exists a k3 such that:
D_{k3}( E_{k1}( E_{k2}( pt ) ) ) = pt
If you take a message, and use huffman encoding with random, secret
labels as encryption, the same cannot be said, except in the special
case where all symbols are equiprobable. Try it and see! Let's take the
alphabet A, B, C, and assume A occurs 2x as often as B and C, producing
the following tree:
*
/ \
A *
/ \
B C
There are 4 labelings:
1) A: 0, B: 10, C: 11
2) A: 0, B: 11, C: 10
3) A: 1, B: 00, C: 01
4) A: 1, B: 01, C: 00
If, as you proposed, randomly labeling a huffman tree is equivilant to a
polyalphabetic substitution, then encoding with one of these, and
decoding with another, is equivilant to doing some (third)
polyalphabetic substitution. Let's take the string "AABACCBA" encode
using labeling (1). This results in "001001111100." Decoding using (3)
results in "BABAAAAAB." According to you, (1) and (3) are
polyalphabetic substitutions, and there is a third polyalphabetic
substitution with which "BABAAAAAB" can be transformed into "AABACCBA".
> most likely still weak because you have to communicate somehow the new
> tree to use.
No matter what, I need to communicate the labelings of the tree. That's
a given. It doesn't make it weak, however, because the communication is
somehow kept private; that's what it's called "secret key
cryptography." No matter WHAT the encryption scheme is, unless it's PK
or QC, the key needs to be communicated. This fact does not weaken the
scheme.
> > By your reconing,
> > this should be easy to solve.
>
> Now you've change the proposal to a poly-alphabet which is still weak.
Now you seem to be really confused. My initial post was asking about
basic static huffman code of letters, where each node has 2 leaves, but
where the labels (0 and 1) are chosen at random. You called it a
poly-alphabet. I made a new proposal, using a static huffman encoding
of words, where each node has 26 leaves, and where the labels are chosen
at random from A-Z. You initially called this an OTP. Now you're
calling it a poly-alphabet?
> > Hmm! This would be an interesting
> > cryptosystem, anyone want to implement it?
>
> It lacks any interesting amount of strength.
For the first one, if there are 26 leaves, then there are 26/2 + 26/4 +
... 1 (which is approximately 26) internal nodes, and 2! labelings for
each node. This means there are (2!)**(numnodes), or about 2**26
different keys.
For the second, there are 1000s of leaves, and (for N leaves) there are
N/26 + N/(26**2) + N/(26**3) + ... + 1 internal nodes, and 26! labelings
for each node. Now there are (26!)**(numnodes) different keys.
> > The point is, the unknown symbol length vastly complicates things,
> > making it quite different from mono-alphabetic substitution.
>
> It doesn't complicate things much at all
> Joe
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Huffman stream cipher.
Date: Wed, 18 Oct 2000 21:43:04 +0200
Benjamin Goldberg wrote:
>
> Because a keyed Huffman coding is a more secure primitive than a
> polyalphabetic substitution, I am proposing an idea to use one as a
> stream cipher. The following is my proposal for generating a psuedo
> random Huffman tree (refered to as a PRHT from now on).
[snip]
In my article of 10.10 entitled 'A general substitution
scheme with variable-length codes' I described a very
general kind of substitution using two arbitrary Huffman
codes (which includes the special case where one of them
is e.g. ASCII) and also mentioned that one can do
'polyalphabetical substitutions', i.e. with a number of
such substitutions and use e.g. a PRNG to select these,
which amounts in fact to a fairly general stream cipher.
I should appreciate your indicating the salient features
of your proposal that are not covered by my article so
that I could learn something from your work. Thanks
in advance.
M. K. Shen
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Wed, 18 Oct 2000 19:33:30 GMT
Tim Tyler wrote:
>
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> : Tim Tyler wrote:
> :> Paul Schlyter <[EMAIL PROTECTED]> wrote:
>
> :> :Java is also designed to to execute on only one single
> :> :architecture, the Java virtual machine, while C was designed to
> :> :execute on many different architectures.
> :>
> :> There's no difference between C and Java in this respect. Java was
> :> designed (from the first white paper) to be compiled to whatever
> :> processing hardware is available. The difference from C in this
> :> respect is that C is often shipped in compiled form, while Java is
> :> almost always compiled on the target machine at some stage before
> :> being executed.
>
> : Untrue, UNLESS you are considering just-in-time compiling to be
> : compiling.
>
> Well, naturally I am consideriung "just-in-time compiling" to be
> compiling.
>
> See the "compiling" there in the name? It is there with good reason.
I was considering "compiling" to mean .java -> .class, whereas you're
considering "compiling" to mean [parts of a] .class -> platform
dependent machine code.
And, if you are considering that... you might want to know that some
.java->.class compilers will also do the .class-> platform dependent
code, for the machine they're on, and include that in the .class file
for faster execution on the targeted platform.
--
"Mulder, do you remember when I was missing -- that time that you
*still* insist I was being held aboard a UFO?"
"How could I forget?"
"Well, I'm beginning to wonder if maybe I wouldn't have been
better off staying abo-- I mean, wherever it was that I was
being held." [from an untitled spamfic by [EMAIL PROTECTED]]
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Enigma: Stolen German Code Machine Turns Up in BBC Mailroom
Date: Wed, 18 Oct 2000 14:34:04 -0500
Andre wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (John Savard) wrote:
> > On Wed, 18 Oct 2000 01:25:23 +0100, Mathew Hendry
> > <[EMAIL PROTECTED]> wrote, in part:
> >
> > >Three of the four rotors are missing. (Why steal only those?)
>
> Its an enigma (sic) why they'd remove the rotors .
>
> Here's my theory why they were removed .
>
> I suspect that it has to do with the secret Tesla files relating to
> zero point energy and wireless power .
>
> As this information was sensitive, after the end of WW2 it was
> encrypted with one of these machines. (best technology available at the
> time) . I suspect that the thieves knew this, as they had gotten hold
> of one of the documents concerned.
>
> Therefore, they needed the original machine that the document(s) were
> encrypted on to read the documents.
>
> This also explains why the rotors were removed.
> (to allow the code wheels to be copied onto computer in order to read
> any other documents they might obtain) ...
>
> Any comments ? (apart from "are you taking your medication" ? :-) )
>
> BTW I would *really* appreciate it if anyone could shed any light on
> this particular theory ...
<snip logical sensible part>
An enigma machine can be easily simulated in software.( Ridiculously easily
to do). The design of this enigma was unusual, but there was nothing that
prevenetd people from using publicly available information to create a
piece of software that would do exactly what it does. The theory is crap.
------------------------------
From: Jon Walker <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Looking for small implementation of an asymmetric encryption
Date: Wed, 18 Oct 2000 20:28:59 +0100
Thanx Mike, had been thinking along the lines off a hash, I will delve
further.......
Jon.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: algo to generate permutations
Date: Wed, 18 Oct 2000 19:26:44 GMT
In article <[EMAIL PROTECTED]>,
Andreas Gunnarsson <[EMAIL PROTECTED]> wrote:
> On Wed, 18 Oct 2000 [EMAIL PROTECTED] wrote:
>
> > I just took a stab at generating only distinct arrangements,
> > http://burtleburtle.net/bob/c/anagram.c
> > It places all occurences of one letter, then all occurences of the
> > next, and so forth. It's bigger and slower than pure permutations,
> > although it only does work proportional to the number of distinct
> > arrangements. It's still not lexicographic order.
>
> It feels like this is a little off topic, but...
>
> I exctracted the algorithm for generating distinct arrangements from
the
> number solving program I made. It is a quite simple non-recursive
> algorithm that generates only distinct arrangements and the output is
> sorted in alphabetic order.
>
> It is available at ftp://ftp.zzlevo.net/pub/src/perm.c if anyone is
> interested.
>
> Andreas
Your code is 2x faster than mine, and half the size, and it does
lexicographic order, and it avoids recursion. Very good!
- Bob Jenkins
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: James Felling <[EMAIL PROTECTED]>
Subject: Re: ---- As I study Rinjdael...
Date: Wed, 18 Oct 2000 14:45:26 -0500
Greggy wrote:
> As I study Rijndael, I am constantly haunted by the question I hope
> someone can answer:
>
> If Rijndael is so strong, why does the US government choose NOT to use
> it for ANY (not all) classified information?
>
> --
> I would prefer to live in a free society than
> a drug free society - even if the latter could
> actually be achieved.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
Well, firstly because NIST does NOT certify algorithims for classified
data, that job falls to the NSA( or so I have been led to believe). So
even if it were to be suitable, the NSA would have to grant it a seperate
certification.
Secondly, It may well endup recieving such a certification at some point
down the road. I am certian that the NSA will want to spend an extensive
amount of time analyzing it to ensure that if they grant such
certification they will not end up with egg on their faces from an
unforeseen weakness. It is my guess that it may well be entering the
initial phases of such certification now.
Lastly, having seperation of algorithims for classified vs. confidential
data is a good thing, as it allows for a secondary point of restriction on
access to the more secure files.( one can secure both the files, and the
decryptor in this case) In addition, it is likely that custom built AES
crackers/ chips to decrypt AES will be substantially cheaper and easier to
make/access than mysterious secure algorithim chips/ crackers. This can
also add to security of data.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Looking for small implementation of an asymmetric encryption algorithm
Date: Wed, 18 Oct 2000 19:51:02 GMT
> It isn't really true that your basic requirement is to
> encrypt your messages. Your real requirements have to do
> with what information needs to be kept private, what it
> is worth, what your potential attackers can do, and so on.
> Also, you may need secrecy, or authentication, or both.
> There are a lot of variations.
>
> For instance, is the low-memory embedded system intended
> to be left alone? Could an attacker grab one and learn
> everything stored in it? Does it have to run without
> help, or would someone (authorized) "log in", as it were?
>
> The best solution always comes from realizing your exact
> requirements, avoiding preconceptions.
Thanks for answering my post.
The max size of the packet sent from the device is actually only 49
bits. I can send infrequent 13-bit messages to the device. The device is
left alone and an attacker could access it and its memory although the
devices will be spread out over a large area so it would be difficult to
vist all of them.
Secrecy is my primary concern. Authentication would be nice but most of
the bits are needed for the payload. The information is timely and need
only be kept secret for a few days. The transmission mechanism is not
entirely reliable and it is possible that messages will get lost (but if
I do get the message I don't believe it will have any corrupt bits).
Device assembly is outsourced and to avoid adding another step to
the process I had hoped that with an asymmetric algorithm all the units
could be programmed with the same public key (or set of public keys and
in case a private key was compromised I could use the 13-bit message to
have the device select another key (although the device would need to
make sure that any 13-bit message was authentic). It would be difficult
to get a new 1024-bit key to a device) but knowing that public key
wouldn't allow an attacker to decrypt the messages coming from any of
the other boxes.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Ray Dillinger <[EMAIL PROTECTED]>
Subject: Re: working with huge numbers
Date: Wed, 18 Oct 2000 20:05:32 GMT
On Mon, 16 Oct 2000, Benjamin Goldberg wrote:
>Ray Dillinger wrote:
>>
>> On Thu, 12 Oct 2000, Benjamin Goldberg wrote:
>> >When you do multiplications, do you use Montgomery form? This isn't
>> >merely a little tweak that gets a tiny increase in performance, it is
>> >a major speed-up.
>>
>> Hmmm. Maybe not. I don't know what you mean by "Montgomery Form".
>> What I do for the first cut is the basic russian algorithm;
>>
<snip>
>
>No, this is definitely not what I meant. Look up Montgomery
>multiplication in the Handbook of Applied cryptography. Your method is
>perfectly ordinary integer multiplication, though not the type I've
>usualy seen used. Montgomery multiplication is quite a bit more
>complex, but also rather faster.
<...After a quick look at HAC...>
Oh, right. I have used that form in a second-tier routine for
*MODULAR* multiplication -- but it doesn't 'win' for general
multiplication. Sorry about the confusion over terms.
By Montgomery form, you mean a vector of residues modulo various
smaller primes, where the smaller primes have a product greater
than the current modulus. Any number smaller than the product
of the smaller primes can be represented uniquely this way, and
most modular arithmetic on this form is more efficient. This is
cool, but when the "modulus" is bigger than the product of the
operands (ie, for general multiplication), you have to include
a greater number of residues to push their representable limit
higher. When working with that number of residues, it is no
more efficient than the russian algorithm.
>> The Exponentiation algorithm I usually use is similar to
>> the first of the two above, except I work with a *copy* of
>> B, which I square each time I process a bit, and multiply
>> the answer buffer by (instead of adding it with a power
>> offset) when processing a one bit.
>That is the most common method of efficient exponentiation that I've
>seen, but it *really* helps if the squaring is optimized, too.
>However, Montgomery also invented an efficient method of exponentiation
>which may be even faster; See HAC.
Ack... has invented an efficient method of *MODULAR* exponentiation
which is *definitely* faster ...
>> However, the "squaring" I do is actually just a call to the
>> multiplication function -- I've learned a faster algorithm
>> for cubing something, but alas, there doesn't seem much call
>> for cubing things.
>There's a way to square a number that's faster than multiplying it by
>itself. It takes advantage of the fact that most of the products of the
>digits (bytes) of the operand are used twice each, eg:
> a b c d
> * a b c d
>====================
> ad bd cd dd
> ac bc cc cd
> ab bb bc bd
>aa ab ac ad
>--------------------
>See how the product ab occurs 2x, as do all the others *except* aa, bb,
>cc, and dd? This means that we can make squaring almost twice as fast
>as multiplying.
Hmmm. That's good incisive thinking. I like it. You just need
to figure out which places in the addition matrix a new word
product needs to be written to between the word multiplies and
the additions. (Hmm, or added to in the accumulating buffer, if
you wanted to avoid allocating a full addition matrix). You
wouldn't want to implement this by memoizing the word multiplication
function, because then you've got a memoization lookup that may
be slower than the multiplication. Hmmmm. Looks like a good
second-tier technique, to use once things are working correctly
and I'm coming back to make things better. But I won't be doing
that unless the application runs uncomfortably slowly without it.
Still, Thank you! :-) This is a useful technique!
I've avoided using an explicit addition matrix in my multiplication
routines, because like the work involved in multiplying, it grows
with the square of the size of the numbers being multiplied. And
you don't even actually need an addition matrix with this squaring
technique either - you can do it all in the accumulator buffer,
same as with russian-algorithm multiplication. But it certainly
is a good form to show off the technique in. Oh, right, and it can
be faster if you've got multiple CPU's and a *really* good compiler.
But I usually assume I'm writing for a single CPU.
>Yeah, sometimes the prefab libraries have interfaces I don't like, or
>use bad style in a way I really dislike. One library I know of for
>working with polynomials in GF(2^N) has the modulo as a global variable,
>rather than as a parameter to the functions it's used in. Worse, the
>structures in which a polynomial is stored are of fixed size, specified
>in a #define in the header, rather than being dynamically allocated.
>You can't, at execution time, decide you want to use a different
>[possibly bigger] modulo... This is kind of like having a bignum
>library that uses a fixed 1024 byte struct for each number instead of
>buffers that're allocated as needed.
Yeah. I started creating "roll your own bignums" libraries way back
when I was working mainly with Pascal. All of the ones I could find
back then had major crocks of one kind or another. I mean, they
worked, and some of them were even fast, but they weren't good mental
hygiene, if you know what I mean.
Bear
------------------------------
** 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
******************************
