Cryptography-Digest Digest #4, Volume #13 Thu, 26 Oct 00 08:13:00 EDT
Contents:
Re: I am after a simple one-way encryption algorithm (those who know me have no need
of my name)
Re: nothing has been posted between 2 am & 12 am today ... ("kihdip")
DES algorithm in Java (S983845)
Re: Storing an Integer on a stream (Andras Erdei)
Re: Hardware RNGs (Tom St Denis)
Re: Is DES without IP/FP just as strong? (Tom St Denis)
Re: Is DES without IP/FP just as strong? (Tom St Denis)
Save RSA bandwidth (John Savard)
Re: Hardware RNGs (Volker Hetzer)
Re: DES algorithm in Java (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Re: Is OPT the only encryption system that can be proved secure? (Tim Tyler)
Re: Is OPT the only encryption system that can be proved secure? (John Savard)
Re: Hardware RNGs (Richard Heathfield)
Re: Is DES without IP/FP just as strong? (Thomas Pornin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Subject: Re: I am after a simple one-way encryption algorithm
Date: Thu, 26 Oct 2000 10:12:28 -0000
<8t4klv$9jn$[EMAIL PROTECTED]> divulged:
>What is the simplest way to encrypt passwords using a one way algorithm
>from a perl script. I wish to hold user passwords in a data file which
>can then be used to validate passwords which are entered.
as has already been mentioned you probably want a hash. many of which are
available from cpan as modules, including md5, ripemd-160, sha, sha-1, &c.
http://www.cpan.org/modules/by-category/14_Security_and_Encryption/
--
okay, have a sig then
------------------------------
From: "kihdip" <[EMAIL PROTECTED]>
Subject: Re: nothing has been posted between 2 am & 12 am today ...
Date: Thu, 26 Oct 2000 12:22:12 +0200
On 24-10 I have about 12 hours with no postings and on 25-10 there is about
9 hours with no postings. (But I really don't have a clue if Outlook Express
states the right time under "sent")
- But I guess you're right.
"jungle" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> today nothing has been posted between 2 am & 12 am ...
> yesterday nothing has been posted between 8 am & 3 pm ...
>
> is this right ?
>
>
------------------------------
From: S983845 <[EMAIL PROTECTED]>
Subject: DES algorithm in Java
Date: Thu, 26 Oct 2000 12:54:05 +0100
Hi,
I want to program the DES algorithm in Java. Does anyone know where I
can find some sample code?
Thanks
------------------------------
From: Andras Erdei <[EMAIL PROTECTED]>
Crossposted-To: comp.compression
Subject: Re: Storing an Integer on a stream
Reply-To: [EMAIL PROTECTED]
Date: Thu, 26 Oct 2000 11:03:48 GMT
Tim Tyler <[EMAIL PROTECTED]> wrote:
>:> IIRC this encoding is asymptotically optimal.
>
>"Severly sub-optimal" is how I would describe it, especially in the
>context of padding schemes.
:O)
>Padding with a format that can't use repeated 1s could only ever be
>anywhere near optimal for small values.
as you'll see, this restriction isn't as severe as one might
think
> The problem is that this runs in the fact of use of the term
>optimal to imply "best". There are other encodings that beat the
>fibonaci one at every stage (except the very early ones).
>By this sort of definition an "asymtotically optimal" runner might always
>come last in the race ;-/
A code is optimal if the average code length (E := sum pi * Li)
is close to the entropy. The most commonly used definition is
"minimal redundancy" (E - H is minimal).
Unfortunately this definition does not scale well, unlike E/H;
so we say that an an encoding is asymptotically optimal if
lim E / H = 1
This definition is used when two conditions hold:
(1) we have an infinite source alphabet (i.e. 1,2,...)
(2) we do not know the probability distribution
if we know it, we can use an optimal encoding (e.g.
Huffman); of course we still have to assume something
about the distribution to be able to create (an
asymptotically optimal) encoding: we assume that we
know the probability ranking (we assume that p1 >=
p2 >= ...)
>If it had been previously determined that this method worked better than
>the self-terminating ones at the head of the thread, it would probably be
>best to use of of those self-terminating methods (or similar) to
>encode such a length.
b( x ) := the binary representation of x
r( x ) := ]log(x)[ zeroes + b( x )
In this case lim E / H = 2 :
Li = ]log(i)[ + [log(i)]
<= 1 + 2 * log( i )
E = sum pi * Li
<= 1 + 2 * sum pi * log( 1 / pi ) = 1 + 2 * H
[here we used several facts, including that pi <= 1 / i
which is easy to prove e.g. indirectly ]
thus this is *not* an a. o. encoding
l( x ) := r( 1 + ]log(x)[ ) + b( x )
In this case lim E / H = 1; this is an a. o. encoding.
[This concept can be applied recursively to shorten the
codeword lengths, but the benefits decrease rapidly (also
you'll see that the Fibonacci encoding is better in practice).]
f( x ) := <fibonacci encoding as described earlier>
In this case lim E / H = 2, just as for r(); OTOH l() is
better than f() only for large values (the transition point
is around 1/2M), so in practice f() is the best one. (And it
shows that my memory does not serve me well, as earlier i
wrote that "IIRC <fibonacci> is a.o." which it is not.)
If you are interested in more detail:
Elias
Universal codeword sets and representations of the integers
IEEE Trans. Inf. Theory 21, 2, 194-203
1975 Mar
Apostolico and Fraenkel
Robust transmission of unbounded strings using Fibonacci
representations
Tech.Rep. CS85-14, Dept. of Applied Mathematics,
The Weizmann Institute of Science, Rehovot, Israel
1985
Fraenkel and Klein
Robust universal complete codes as alternatives to Huffman codes
Tech.Rep. CS85-16, Dept. of Applied Mathematics,
The Weizmann Institute of Science, Rehovot, Israel
1985
>:> Since when larger and larger values are used, methods which can use a
>:> greater range of symbols will systematically trounce it, it's hard to
>:> see how it could be described as "asymtotically optimal".
>
>: What do you mean "a greater range of symbols?" There are only two
>: different symbols at the bit level, 0 and 1. The integer 15 is stored
>: as 8 bits, including the terminator.
>
>Symbols which include the "...11..." sequence in their bodies are
>excluded. Many systems allow a greater range of symbols in the body of
>the representation of the value. One was given at the head of the thread
>- use base 255 and use a 255 terminator. That way you get 255 symbols
>available in each byte (out of a possible 256).
>
>Of course there's a cost incurred at the end of the value of doing this.
>However, the cost is fixed (in this case it's 8 bits). By contrast, the
>cost of not allowing any "...11..." symbols is incurred through the
>representation of the value - and thus grows with the value.
I think you are mistaken -- the cost is not fixed, due to the
fact that as you mentioned you can use only 255 values of the
possible 256.
>: As for byte level encodings, what method would you suggest as being
>: best?
>
>AFAIK, there is no single best method - which is best depends on the
>expected size of the value.
That's true - you have to know the probability distribution to
determine an optimal code.
>I don't really know what's best when, instead I present some indications.
>
>I believe using a self-terminating representation in base N with a N
>terminator/divider is pretty good, though you can probably do better if
>the expected distribution of values is non-uniform, or if the expected
>range of values is known to be small.
>
>To deal with N not being a power of 2 (and thus with the resultant
>file not filling a whole number of bytes) one could use Matt Timmerman's
>method of transforming the result to a finitely odd file, and then
>applying his bijection between such data and 8-bit granular files.
As he mentioned, his proposal only works if additional
assumptions are met -- i.e. the side information of the file
size is present (so you can't use it to trasmit the data
over a channel). [Or e.g. the data you are encrypting is
uniquely decodable (it's a prefix code), in which case you do
not need to encode the length at all :O)]
Also, i think his method does not statisfy the requirement
which started this tread -- there'll be bits in the plaintext
which are more likely to be zero than one, only there'll be
fever of them than in the case of encoding the whole length
using a fixed number of bits.
Br,
Andras
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Thu, 26 Oct 2000 11:05:19 GMT
In article <[EMAIL PROTECTED]>,
Cameron <[EMAIL PROTECTED]> wrote:
> Why don't you just use soundcard input?
> pipe it into a file. It should be pretty darned random.
Um not really.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Is DES without IP/FP just as strong?
Date: Thu, 26 Oct 2000 11:08:19 GMT
In article <[EMAIL PROTECTED]>,
Pascal JUNOD <[EMAIL PROTECTED]> wrote:
> > Yes, without the IP/IP' the cipher is weak when in a CFB-m mode
where
> > m<64.
>
> Never heard about such a weakness... Could you give an (academic)
> reference on this ?
> How weak ?
http://www.esat.kuleuven.ac.be/~cosicart/ps/VR-9300.ps.gz
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Is DES without IP/FP just as strong?
Date: Thu, 26 Oct 2000 11:08:01 GMT
In article <8t8nss$9ve$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Thomas Pornin) wrote:
> According to David C. Barber <[EMAIL PROTECTED]>:
> > After all these years of analysis, has a reason ever been found for
> > the initial/final permutation?
>
> These permutations have no influence on security (since they are
> easily inversed). The usual explanation is hardware-oriented: these
> permutations make DES easier to plug on an 8-bit parallel bus (with
> this permutation, you assemble the 64-bit data with eight 8-bit shift
> registers, which is technologically easier to build than a 64-bit
shift
> register that must be shifted 8 times in each clock cycle).
That's just plain wrong my friend.
http://www.esat.kuleuven.ac.be/~cosicart/ps/VR-9300.ps.gz
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Save RSA bandwidth
Date: Thu, 26 Oct 2000 11:13:04 GMT
Since RSA or Diffie-Hellman with a key of 768 bits is compared to a
conventional cipher with a key of 128 bits, a single public-key block
contains more bits than one needs to establish secure symmetric-key
communications.
Thus, the notion I am about to describe here - while it could
theoretically be patented, if I hadn't gone and given it away, as I am
about to do - is perhaps useless.
Let us suppose that instead of having just one RSA public key/private
key pair, I have a bunch of them. For example, say that I have nine of
them: (e1, M1)/d1, (e2, M2)/d2... (e9, M9)/d9
Furthermor, the nine moduli are (of course) all different - but they
are sorted here so that M1 is the smallest, and M9 is the largest.
Someone sends a message x to me, where x is a number less than M1, by
sending me the following:
(((((((((x^e1) mod M1)^e2 mod M2)^e3 mod M3)^e4 mod M4) ... )^e9 mod
M9
Unlike EKE, there is no privacy amplification: all nine keys are
public, so cracking this is only nine times harder than cracking RSA
once.
So, what is the point? This system is not secure unless a _single_
layer of RSA, with the kind of moduli used, is secure.
But _given_ that a single layer of RSA is secure, in addition to
having transmitted securely the message x, all the intermediate
encrypted quantities are also transmitted securely:
I, and the person sending me the message x, are the only two people
who know, not just x, but also
(x^e1) mod M1
((x^e1) mod M1)^e2 mod M2
(((x^e1) mod M1)^e2 mod M2)^e3 mod M3
...
((((((((x^e1) mod M1)^e2 mod M2)^e3 mod M3)^e4 mod M4) ... )^e8 mod M8
Note, however, that while none of these quantities can be used to
determine the _preceding_ one, each one can be used to determine the
_following_ one with only the public keys.
In addition to transmitting a message, x, which _could_ be random key
material, if one chooses, one has, in the same block, without the
consumption of additional bandwidth, transmitted *eight blocks* of
random key material.
While it is not clear this is really useful for anything:
a) if one has a hash function that one trusts, simply applying it
repeatedly to x can produce large quantities of secure key material
without using public-key computations, and
b) if one is willing to do large-number arithmetic, one could simply
use x as the seed to Blum-Blum-Shub
it at least provides another alternative.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Thu, 26 Oct 2000 13:23:18 +0200
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Cameron <[EMAIL PROTECTED]> wrote:
> > Why don't you just use soundcard input?
> > pipe it into a file. It should be pretty darned random.
>
> Um not really.
Then use it (and the previous hash) as input to sha to get
160 bit of random data. Repead as needed.
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: [EMAIL PROTECTED] (Gisle =?iso-8859-1?Q?S=E6lensminde?=)
Subject: Re: DES algorithm in Java
Date: 26 Oct 2000 11:26:40 GMT
In article <[EMAIL PROTECTED]>, S983845 wrote:
>Hi,
>
>I want to program the DES algorithm in Java. Does anyone know where I
>can find some sample code?
>
>Thanks
>
Cryptix has opens source implementations of both DES and 3DES
and many other ciphers.
http://www.cryptix.com/
--
Gisle S�lensminde ( [EMAIL PROTECTED] )
With sufficient thrust, pigs fly just fine. However, this is not
necessarily a good idea. It is hard to be sure where they are going
to land, and it could be dangerous sitting under them as they fly
overhead. (from RFC 1925)
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Reply-To: [EMAIL PROTECTED]
Date: Thu, 26 Oct 2000 11:04:12 GMT
Peter Thorsteinson <[EMAIL PROTECTED]> wrote:
:> As far as I am aware, only the OTP can be -proved- secure, because "one
:> half is 100% dependent on the other half," and there is, provably, zero
:> relationship from one to the other.
: Thats what I am looking for! id there a refernce?
Applying a conventional OTP, and then applying DES produces a system with
better properties than a traditional OTP alone - in that it resists
bitflipping better.
One criterion for such a "perfect" cyphersystem is that you need to have a
keyspace of size greater than or equal to the size of the message - so
that all possible decrypts are possible and equally likely.
There are an infinity of systems which meet this criterion - not just an
XOR-based OTP.
OTPs don't generally have good security properties, due to poor key
distribution properties - which helps explain their relative neglect.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Thu, 26 Oct 2000 11:27:40 GMT
On Thu, 26 Oct 2000 00:14:31 GMT, "Peter Thorsteinson"
<[EMAIL PROTECTED]> wrote, in part:
>What I would love to know is whether or not (theoretically)
>there is no possible perfect cypher other than the OTP, and a mathematical
>proof would be nice, but even just a citation rom a recognized cryptography
>expert would do fine.
Well, Claude Shannon did note that the theoretical OTP - or its
equivalents, because one can devise a cipher which is not exactly the
OTP, but which is the OTP in disguise - is the only cipher which can
be proven to have _information-theoretic_ security.
The proof no non-OTP cipher has this security is simple enough:
If you have a ciphertext of N bits, enciphered by a system with fewer
than 2^N possible keys, then by trying every single key, you have
obtained fewer than 2^N plaintexts, which are the only possible
plaintexts. Hence, you were able to gain information about the
plaintext.
But Claude Shannon described another *kind* of security, security
based on the "work factor".
If the number of keys is very large for a cipher, then one does not
have time to try them all, even if the number is not large enough to
destroy the information about the plaintext that is still
intrinisically present in the ciphertext.
The trouble is, of course, that ciphers can be broken by other methods
than just trying every possible key.
If you know the answer to a mathematical problem, it's easy to prove
that solving it is not more difficult than applying the method you
already know about. However, proving that there isn't an easier method
that you _don't_ know is another matter.
The famous "halting problem" proof tends to indicate that doing this
isn't just hard, but is in fact impossible.
So it does seem that one can't prove that a cipher is hard to break in
that sense. There _are_ proofs that many ciphers - particularly
public-key ciphers - are *as hard to break* as solving a given
mathematical problem, such as factoring.
But a proof that factoring really is hard is, so far, the sort of
thing that is beyond the reach of mathematics.
In complexity theory, P != NP has not been proved, so we don't
currently know if any really hard problems even exist right now.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Thu, 26 Oct 2000 12:34:40 +0100
From: Richard Heathfield <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Cameron <[EMAIL PROTECTED]> wrote:
> > Why don't you just use soundcard input?
> > pipe it into a file. It should be pretty darned random.
>
> Um not really.
Clearly, you have never heard my singing.
--
Richard Heathfield
"Usenet is a strange place." - Dennis M Ritchie, 29 July 1999.
C FAQ: http://www.eskimo.com/~scs/C-faq/top.html
K&R Answers: http://users.powernet.co.uk/eton/kandr2/index.html
------------------------------
From: [EMAIL PROTECTED] (Thomas Pornin)
Subject: Re: Is DES without IP/FP just as strong?
Date: 26 Oct 2000 12:04:15 GMT
According to Tom St Denis <[EMAIL PROTECTED]>:
> http://www.esat.kuleuven.ac.be/~cosicart/ps/VR-9300.ps.gz
You have not read carefully enough this paper, my friend. The
cryptographic meaning of the final permutation is related to the
feedback mode, which was supposed to increase security. Note that the
attack is against a reduced DES, and is less efficient than other known
attacks against the same reduced DES core (linear cryptanalysis on
8-round DES requires only 2^20 known plaintexts).
In other words, the FP allows more direct access to the weaknesses of a
weakened DES core when used with that special chaining mode, whose job
was to hide those weaknesses. The attack is on the chaining mode, then.
One could produced a CFB-like mode, which included IP^{-1} just before
the DES core, and IP juste after, and then the presence of IP and FP in
DES would just enhance security.
The whole thing means that one should not rely on outer unkeyed bit
manipulations to give security. CFB chaining mode is such an attempt,
and it fails. IP and FP do not give neither take away security from the
full DES core, but they happen to hinder the CFB attempt to increase
security around a reduced DES core. The CFB mode is the weak point
there. Do whatever chaining you want, as long as the cryptographic
engine is strong. If the engine is weak, some chaining modes may reveal
such weaknesses, or somehow hide them, but you are doomed anyway.
--Thomas Pornin
------------------------------
** 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
******************************
