Cryptography-Digest Digest #2, Volume #13 Wed, 25 Oct 00 23:13:00 EDT
Contents:
Re: Factoring Polynomials ([EMAIL PROTECTED])
Re: New Cipher ([EMAIL PROTECTED])
Re: Factoring Polynomials (Simon Johnson)
Re: Is OPT the only encryption system that can be proved secure? (Terry Ritter)
Re: New Cipher (SCOTT19U.ZIP_GUY)
Re: Is OPT the only encryption system that can be proved secure? ("Peter
Thorsteinson")
Re: DATA PADDING FOR ENCRYPTION (Tim Tyler)
Re: Is OPT the only encryption system that can be proved secure?
([EMAIL PROTECTED])
Re: New Cipher (Tim Tyler)
Re: Is OPT the only encryption system that can be proved secure? (stanislav shalunov)
Re: Factoring Polynomials (Nicholas Hopper)
Re: Is OPT the only encryption system that can be proved secure? (Sundial Services)
Re: Is OPT the only encryption system that can be proved secure? ("Peter
Thorsteinson")
Re: Is OPT the only encryption system that can be proved secure? ("Peter
Thorsteinson")
LinuxSecurity.com Speaks With AES Winner (Dave Wreski)
Re: Is OPT the only encryption system that can be proved secure? ("Peter
Thorsteinson")
Re: Is OPT the only encryption system that can be proved secure? (stanislav shalunov)
Re: Factoring Polynomials (Bob Silverman)
Re: Is OPT the only encryption system that can be proved secure? (SCOTT19U.ZIP_GUY)
Re: Is DES without IP/FP just as strong? ("Scott Fluhrer")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Factoring Polynomials
Date: Wed, 25 Oct 2000 22:59:20 GMT
In article <8t7nr1$65g$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Is factoring polynomials also an NP problem for large order
> polynomials just as factoring an integer is?
>
> If so, it should be possible to make a type of RSA using polynomials
> yeah? - Just an idea. :)
Yes it is possible, but if I remember correctly, the strength is the
same as the RSA problem (with minor exceptions), and the time taken is
much longer.
If you're interested you may be interested in "Security Analysis of RSA-
type Cryptosystems" by Marc Joye, it's his PhD paper, and very
enlightening on the matters. I can send you a copy via e-mail if you'd
like.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: New Cipher
Date: Wed, 25 Oct 2000 22:56:38 GMT
> I therefore a reason that replacing a Self-Shrinking LFSR would be
> fast and probably more secure. Who knows?
I'll look into it.
I'm not so sure about the using a hash in a way it wasn't designed. I
chose a hash because it provides very fast diffusion, even given a
large portion of the inputs it is not reversible, and it is a standard
design block. It would certainly be possible to make it faster,
there're dozens (if not hundreds) of faster ciphers, this was primarily
an experiment in a new use of a hash. Thank you for the comments
though, I hadn't even considered use a Self Shrink LFSR.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Factoring Polynomials
Date: Wed, 25 Oct 2000 23:08:36 GMT
In article <8t7ok5$6nv$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> In article <8t7nr1$65g$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > Is factoring polynomials also an NP problem for large order
> > polynomials just as factoring an integer is?
> >
> > If so, it should be possible to make a type of RSA using polynomials
> > yeah? - Just an idea. :)
> Yes it is possible, but if I remember correctly, the strength is the
> same as the RSA problem (with minor exceptions), and the time taken is
> much longer.
>
> If you're interested you may be interested in "Security Analysis of
RSA-
> type Cryptosystems" by Marc Joye, it's his PhD paper, and very
> enlightening on the matters. I can send you a copy via e-mail if you'd
> like.
> Joe
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Indeed, don't use my enclosed e-mail address use:
[EMAIL PROTECTED]
The address supplied here can no longer be retrieved. I forgot my
rather long, random password :)
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Wed, 25 Oct 2000 23:27:56 GMT
On Wed, 25 Oct 2000 23:06:26 GMT, in
<SHJJ5.39299$[EMAIL PROTECTED]>, in sci.crypt "Peter
Thorsteinson" <[EMAIL PROTECTED]> wrote:
>This much I know:
>Currently, it is commonly accepted that the xor-based one time pad (OTP) is
>the only perfectly secure cipher encryption system that has been
>mathematically proven impregnable by way of cryptanalysis.
Alas, *I* do not accept any such thing.
The mathematically-proven OTP depends upon various assumptions which
cannot be provably achieved in practice. And proof based on
unprovable assumptions is ultimately no proof at all. See my extended
comments, for example:
http://www.io.com/~ritter/GLOSSARY.HTM#OneTimePad
>No other
>encryption systems currently in the public knowledge have been proven
>secure.
No, I think there are several other systems with similar "proofs" and
assumptions, although I have not collected a list of references.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: New Cipher
Date: 25 Oct 2000 23:25:23 GMT
[EMAIL PROTECTED] wrote in <8t7m4s$4l4$[EMAIL PROTECTED]>:
snip
>>How does one know that 1000 to fill
>> the space is not really part of the orignal file.
>Because you know the length of the KEY, there is no file involved with
>this, only a key and a block.
sorry I confused this with another post where the 01 0202 ..
fill was being discussed so I nver read past the fill issue.
Hay I never said I was perfect live with it.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: "Peter Thorsteinson" <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Thu, 26 Oct 2000 00:14:31 GMT
Cool, and thanks. Actually, I am more interested in the Theoretical One Time
Pad! I very much appreciate your distinction against the Realized One Time
Pad, the crux of which the assumption of a physically realized, perfectly
random source. 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.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: DATA PADDING FOR ENCRYPTION
Reply-To: [EMAIL PROTECTED]
Date: Wed, 25 Oct 2000 23:44:01 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: I did a search of the internet for IEEE encryption padding [...]
Here's an existing padding method:
http://www.cix.co.uk/~klockstone/bookends.htm
This is more along the lines of padding out a file with random garbage
(rather than increasing its size to a multiple of the existing block
size).
It pads with PRNG data. Surely this is a bad idea.
It does appear that until recently there were zero bijective schemes for
mapping a n-byte file to a file which is a multiple of the block size of
an orthodox block cypher.
In the absence of many block cyphers with variable-size blocks, use of
such algorithms appear to be superior to existing padding schemes -
in terms of avoiding potential security problems.
Something simple like appending a 1 and padding with 0s to the end of the
block can allow up to 2^128 - 1 out of 2^128 keys to be rejected without
any further knowledge of the plaintext - possibly enough to reject all but
one message.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Thu, 26 Oct 2000 00:08:01 GMT
I agree with Ritter on this one. There are many systems that have
proofs of security, and they all have varying assumptions. The
assumptions for OTP are fairly simple, a OTP qualifying encryption
algorithm, and a truly random pad. We have examples of the first (XOR
is the most common), but the second we have no proof of existance.
The same applies to other systems, for example in the AES competition
DFC had a proof of security against differential attacks, it fell to a
different attack.
BEAR and LION have proofs of security with certain assumptions, all
that means is that those assumptions must be violated.
The variable levels of proof can range from, proving the encryption
algorithm is not an apple (that is to say it is literally not a kind of
fruit known by the name apple), to proving that under certain
assumptions it is perfectly secure, to proving information theoretic
security, to proving absolutely nothing. Also the various attacks on
ciphers can be seen as proofs in their own way, they are proofs of the
maximum security offered by that cipher. Take your pick there are so
many different kinds and levels of proof that even a canonical
reference would be lacking by the time we finished writing it.
> any references, I would much appreciate it.
There are a great many of them, but just as Ritter did not, I do not
have any references handy.
Joe
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: New Cipher
Reply-To: [EMAIL PROTECTED]
Date: Wed, 25 Oct 2000 23:55:15 GMT
SCOTT19U.ZIP_GUY <[EMAIL PROTECTED]> wrote:
: [EMAIL PROTECTED] wrote in <8t79vl$pba$[EMAIL PROTECTED]>:
:>I have a currently unnamed cipher design sitting
:>here in front of me. [...]
:>
:>First let me define the primitive, the primitive
:>that I will call SHA, is SHA-256 WITHOUT the
:>final counter, so if padding needs to be done, it
:>is done using a 1 followed by 0s to fill the
:>space, I've avoided the need for padding as much
:>as possible
: Do you mean your avoiding trying to solve the
: problem of padding. How does one know that 1000 to fill
: the space is not really part of the orignal file.
Appending a 1 followed by enough zeros to fill to the end of
the block is unambiguously reversible.
If ...1000 was part of the original file, it would become
...10001000...000 after padding was applied.
I suppose padding with zeros is simple and fast. I'm not convinced that
this justifies all the resulting probable known plaintext, though.
The SHA counter is compulsory for a hash function - but I believe in
other contexts - e.g. when using a SHA-like algorithm in a counter mode
to produce a PRNG - it appears to be an unnecessary waste of space.
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: 25 Oct 2000 20:59:21 -0400
"Peter Thorsteinson" <[EMAIL PROTECTED]> writes:
> This much I know:
> Currently, it is commonly accepted that the xor-based one time pad
> (OTP) is the only perfectly secure cipher encryption system that has
> been mathematically proven impregnable by way of cryptanalysis.
OTP is trivially vulnerable to active attacks. If your bank used OTP
to encrypt transactions (very non-practical solution for key
distribution reasons), and used a specific record type, it would be
trivial to flip the highest bit in the "amount" field, presumably
ending up with vigintillions of dollars.
> No other encryption systems currently in the public knowledge have
> been proven secure.
Oh, this cryptosystem is as secure as OTP:
Given message M and truely random key K, twice longer than M, to
encrypt M with K one throws away every other bit of K (say,
even-numbered bits) and XORs M with odd-numbered bits of K.
--
Stanislav Shalunov <[EMAIL PROTECTED]> Internet Engineer, Internet2
"Engels, and before him Hegel, pointed to the numerous contradictions
that abound in mathematics." -- Alan Woods
------------------------------
From: Nicholas Hopper <[EMAIL PROTECTED]>
Subject: Re: Factoring Polynomials
Date: Wed, 25 Oct 2000 21:00:11 -0400
Polynomial Factorization is indeed in NP, since given the alleged factors
I can multiply them together and verify the result. However, I think
you meant to ask if it was NP-Hard (by the way, factoring isn't *) and
it's not. In fact, factoring polynomials over the rationals is in P. The
famous LLL lattice basis reduction algorithm was actually published as
part of a paper (by Lenstra, Lenstra and Lovasz) which gave an O(n^12 log
n) algorithm to factor polynomials over the rationals. I'm no expert, but
I believe we now know faster algorithms. (On a related note, polynomial
gcd is in NC, but there is no known efficiently parallel algorithm for
integer gcd)
That said, the NTRU cryptosystem uses polynomials over the integers mod
p and is vaguely RSA-like.
-Nick
(* if factoring is NP-hard then the polynomial heirarchy collapses to
\Sigma_2, and that would be about as surprising as P=NP)
On Wed, 25 Oct 2000, Simon Johnson wrote:
> Is factoring polynomials also an NP problem for large order
> polynomials just as factoring an integer is?
>
> If so, it should be possible to make a type of RSA using polynomials
> yeah? - Just an idea. :)
>
>
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
>
------------------------------
Date: Wed, 25 Oct 2000 18:12:21 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Is OPT the only encryption system that can be proved secure?
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.
Now... when one says that the OTP is "secure," that does assume that no
one has a copy of that one-time pad! That it has never been left on a
secretary's desk or left in a CD-ROM drive or that any one of a hundred
zillion things did not go wrong. For example, a Soviet one-time pad
system WAS invaded for many years. That's because it was not "as
secure, as-implemented, as they thought it would be." Everything in the
OTP system depends on perfect deployment, garble-free transmission,
perfect use -- in other words, perfect human beings. And there's the
rub.
>Peter Thorsteinson wrote:
>
> This much I know:
> Currently, it is commonly accepted that the xor-based one time pad (OTP) is
> the only perfectly secure cipher encryption system that has been
> mathematically proven impregnable by way of cryptanalysis. No other
> encryption systems currently in the public knowledge have been proven
> secure.
>
> Now, my question is:
> Has there been any mathematical proof developed that shows that the OTP is
> the only encryption system that can be provably secure. If anyone knows of
> any references, I would much appreciate it.
------------------------------
From: "Peter Thorsteinson" <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Thu, 26 Oct 2000 01:43:03 GMT
Cool, and thanks.
------------------------------
From: "Peter Thorsteinson" <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Thu, 26 Oct 2000 01:45:27 GMT
> Oh, this cryptosystem is as secure as OTP:
> Given message M and truely random key K, twice longer than M, to
> encrypt M with K one throws away every other bit of K (say,
> even-numbered bits) and XORs M with odd-numbered bits of K.
Can that not be shown to be homologous?
------------------------------
From: [EMAIL PROTECTED] (Dave Wreski)
Subject: LinuxSecurity.com Speaks With AES Winner
Date: 25 Oct 2000 21:47:13 -0500
In this interview Vincent Rijmen talks about the development of the
Rijndael algorithm, his selection as the NIST algorithm of choice for AES,
thoughts on Linux and security, and the future of Internet security.
"Rijndael takes its name from its creators' last names, and beat out
finalists including those from IBM, RSA, Counterpane, and the Serpent
algorithm developed by a group of European cryptographers. AES will soon
replace DES as the standard algorithm for encrypting sensitive data. It
has been reported that even a machine capable of breaking the old DES
standard in a second would take some 149 trillion years to crack the
proposed AES's lowest level of security."
http://www.linuxsecurity.com/feature_stories/interview-aes.html
------------------------------
From: "Peter Thorsteinson" <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: Thu, 26 Oct 2000 01:47:55 GMT
> 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?
------------------------------
From: stanislav shalunov <[EMAIL PROTECTED]>
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: 25 Oct 2000 22:08:59 -0400
"Peter Thorsteinson" <[EMAIL PROTECTED]> writes:
> Can that not be shown to be homologous?
Define homologous ciphers.
--
Stanislav Shalunov <[EMAIL PROTECTED]> Internet Engineer, Internet2
A language that doesn't have everything is actually easier to program
in than some that do. -- Dennis M. Ritchie
------------------------------
From: Bob Silverman <[EMAIL PROTECTED]>
Subject: Re: Factoring Polynomials
Date: Thu, 26 Oct 2000 02:08:12 GMT
In article <8t7nr1$65g$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> Is factoring polynomials also an NP problem for large order
> polynomials just as factoring an integer is?
You seem to have a bit of confusion. Both problems are trivially
in NP.
You can not mean NP-Complete in place of NP, because factoring integers
is not known to be NP-Complete. Nor is it known to be in P.
OTOH factoring polynimials is known to be in P (polynomial in the
degree; not in the size of the coefficients)
What do you really mean here????
--
Bob Silverman
"You can lead a horse's ass to knowledge, but you can't make him think"
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Is OPT the only encryption system that can be proved secure?
Date: 26 Oct 2000 02:15:10 GMT
[EMAIL PROTECTED] (Peter Thorsteinson) wrote
in <HHKJ5.39842$[EMAIL PROTECTED]>:
>Cool, and thanks. Actually, I am more interested in the Theoretical One
>Time Pad! I very much appreciate your distinction against the Realized
>One Time Pad, the crux of which the assumption of a physically realized,
>perfectly random source. 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.
>
>
Actaully the only reason a OTP used in the correct way is secure
is becuase if one has cipher text there can be more than one possible
solution. Most real world ciphers are not secure in this sense take
PGP for example. It is not secure at all in this sense becasue of the
public key. But one can encrypt with PGP not using a public key so
that only the main cipher is in use. But even in this case PGP is not
secure since there may only be one key that unlocks the cipher and
that key is the one that gives the anwser.
To get close to a secure cipher one should compress bijectively
as small as possible and then use encryption in a bijective way
however none of the big boys do this in the open literature and
most portocols are desinged not to do this. I feel scott19u is
secure with my compression since there exist many possible solutions
and the more false solutions the more secure. But if you keep
using the same types of files and same key after a while even it
is not theoritically secure.
However no method that is completely repeatable is secure
against a plain text attack. If the same key is used twice.
One could defeat this by changing key every time or add the use
of secret random numbers.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Is DES without IP/FP just as strong?
Date: Wed, 25 Oct 2000 19:37:10 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:8t7kt5$3jd$[EMAIL PROTECTED]...
> In article <8t7hp9$10q7$[EMAIL PROTECTED]>,
> "David C. Barber" <[EMAIL PROTECTED]> wrote:
> > After all these years of analysis, has a reason ever been found for
> the
> > initial/final permutation? I know it's not [true] DES without it,
> but has
> > it ever been found to strengthen or weaken the cipher?
>
> Yes, without the IP/IP' the cipher is weak when in a CFB-m mode where
> m<64.
>
I've heard this before, but I haven't seen any proof (or even a
demonstration). Do you have a reference?
--
poncho
------------------------------
** 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
******************************
