Cryptography-Digest Digest #717
Cryptography-Digest Digest #717, Volume #13 Mon, 19 Feb 01 16:13:01 EST
Contents:
A seriously different cipher concept (long) ("Paul Pires")
From: "Paul Pires" [EMAIL PROTECTED]
Subject: A seriously different cipher concept (long)
Date: Mon, 19 Feb 2001 12:33:32 -0800
The following is a description of a cipher concept I
have been working on for quite awhile. It's reason
for existence is to explore a different method that
has the potential for being unusually fast. All rights
are preserved. Some or all of this material may be
covered by patents held by the author or unknown
others. No presentment is made that the methodology
contained herein is suitable, safe or unencumbered for
commercial use.
The complete description in PDF format including
source code and test results can be found at:
http://www.outsorcery.com/Pires/pires.html
An executable suitable for running under Windoze
can also be downloaded. This program randomly
re-keys the cipher, encrypts 10Megabytes of
zeros and writes the output to a file "Data.bin" in
a format suitable for testing with diehard or other
analysis packages.
I would appreciate any comments or observations
that any might have on this material.
Thank you,
Enefinef:
Paul Pires 02/10/01
Section 1, Introduction:
This paper is meant to explore the advantages and disadvantages of a
structure that is driven by internal states like a stream cipher but which
processes information in block fashion. The discussion is presented in three
parts, General description, detailed description and appended support
information containing example source codes and reports on randomness
testing.
An objective of this discussion is to show a very fast method of stream
encryption that avoids many of the draw-backs of simple XOR stream
ciphers such as known plaintext attacks and bit-flipping.
Contents:
Section 2, General description specifications:
Section 3, Brief walkthrough:
Section 4, Detailed walkthrough:
Section 5, Arguments for security:
Section 6, Required support:
Section 7, Design decisions justifications:
Section 8, Variations: (Omitted)
Section 9, Conclusion:
Section 10, Appendix: (Omitted)
Section 2, General description specifications:
Although described as a stream cipher, this method implements the algorithm in
block "cycles". Each cycle, the algorithm completely processes the text for an
entire "block", 2048 bits in this case. The algorithm runs once per cycle,
stepping through each element of the block. There are no recursive "rounds", one
pass and the block is encrypted or decrypted.
The specifications of this proposed cipher are as follows:
· Encrypts / decrypts at 5.4 clocks per byte (8 bits). (1)
· Has not failed extensive random testing. (2)
· Naturally authenticates and resists bit flipping attacks.
· Uses only simple bitwise operations, SHIFT, AND, OR, XOR.
· Simple key set-up and unique IV implementation.
· Variable block and key size, easily implemented.
Like a conventional stream cipher, this cipher maintains a key dependent
internal state, it uses a portion of that state to encrypt-decrypt text and then
modifies the internal state in a pseudo random way before repeating these
operations on the next increment of text.
Unlike a conventional stream cipher, this method maintains it's internal state
in the form of two different tables of values, each treated separately according
to different rules. It is the cooperation and interplay between these two tables
that forms the PRNG function and also accounts for the desirable properties
cited above. It is this interplay that this paper is meant to address. Each of
the two state tables is simple and ineffective in its construction and operation
when viewed alone but together, they support and cooperate so that the
characteristics of one complement and support the other.
Two unusual concepts are presented here. The first oddity is the notion that a
formidable process (a Cryptographically secure PRNG) can be built from two
simplistic mechanisms that are designed to cooperate advantageously. The second
is that a simple XOR stream cipher can be made to have many of the advantages of
a block cipher, not by adding complex functions, but merely by re-arranging the
interaction of existing simple actions.
Section 3, Brief walkthrough:
The major components of this cipher are the two state tables (AB), tables for
temporarily storing the plaintext - ciphertext and a static table defining a
selection of different relative changes that can be imposed on state A. Before
getting to the walkthrough of a cycle, a description of these components might
be helpful.
· State table A, a 64-entry table initialized with the values 0-63 in a known
starting order. No omissions, no duplications.
· State table B, a 64-entry table sized to operate on the same unit siz
Cryptography-Digest Digest #717
Cryptography-Digest Digest #717, Volume #12 Tue, 19 Sep 00 13:13:00 EDT
Contents:
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an alternative
intorduction] (John Savard)
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption (John Savard)
Software patents (Robert Harley)
Re: A conjecture - thoughts? (Matthew Skala)
BUG In CryptLib3 - by Peter Gutmann. Is there a fix? - Additional info
([EMAIL PROTECTED])
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an ("John A.
Malley")
Re: Double Encryption Illegal? ("Trevor L. Jackson, III")
Re: Double Encryption Illegal? ("Trevor L. Jackson, III")
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an alternative
intorduction] ("Kostadin Bajalcaliev")
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an alternative
intorduction] ("Kostadin Bajalcaliev")
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption ("Kostadin
Bajalcaliev")
Re: Question on self-shrinking ("Trevor L. Jackson, III")
Re: "Secrets and Lies" at 50% off (Albert Yang)
Re: A conjecture - thoughts? (John Myre)
Re: Software patents are evil. (Albert Yang)
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an (Mok-Kong Shen)
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an
alternative intorduction]
Date: Tue, 19 Sep 2000 14:46:50 GMT
On Tue, 19 Sep 2000 01:22:45 -0400, "Douglas A. Gwyn"
[EMAIL PROTECTED] wrote, in part:
Kostadin Bajalcaliev wrote:
... here what Aristotle have to say for his own time:
That's funny, because Aristotle's views on physics are not
held in high regard by physicists.
However, physicists haven't prefered Thales, who proposed that
everything was made of water, and this is what Aristotle was arguing
against in the passage quoted. They agree that energy exists in
addition to matter, and that form and pattern are also realities. So
even if Aristotle did indeed make many mistakes in the physical
sciences, what he is trying to say in that passage is not something
that physicists today would disagree with.
On the other hand, perhaps physicists do believe in a single essence,
although some opt for the geometry of space-time and others for the
wave function.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
--
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption
Date: Tue, 19 Sep 2000 14:57:01 GMT
On Tue, 19 Sep 2000 01:40:59 +0200, "Kostadin Bajalcaliev"
[EMAIL PROTECTED] wrote, in part:
After years of research finally thesis covering my theory of polymorph
encryption is available at:
http://home.cyberarmy.com/kbajalc/algo/pme
The thesis discusses a new approach in Block-cipher design originally
introduced in my thesis about ANIGMA block-cipher in 1997.
That, of course, predates Quadibloc II, the first cipher in which I
include an operation which could be either addition or XOR depending
on functions of the block being enciphered.
So I will soon be including a brief mention of Mr. Bajalcaliev on my
web page; FROG, of course, included a different type of polymorphism,
and I'm sure there are earlier examples; I don't know if it is really
possible to attribute credit for this concept, except perhaps to the
SIGABA: but while that includes what I refer to as indirection, it
doesn't use the output from the control rotors to decide to replace
the cipher rotors by a Hagelin machine, which is what 'polymorphism'
seems to mean in this context.
The specific type of polymorphism in Konstantin Bajalcaliev's designs,
though, as you can see from looking at Quadibloc II and the others of
my designs which use it, was basically added almost as an
afterthought, which is why it is present only in such a rudimentary
form.
If one thinks of not simply choosing between +, -, XOR, and
multiplication, but of choosing from a large collection of Latin
squares, there is of course Terry Ritter to think of, but I don't
think he ever made the choice of Latin square _data_ dependent.
My suspicion is that polymorphism has been around a long time, but
mostly in amateur designs. But there may be something in the publicly
known history of cryptography that is properly considered to be its
origin.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
--
From: Robert Harley [EMAIL PROTECTED]
Subject: Software patents
Date: 19 Sep 2000 17:18:36 +0200
Runu Knips writes:
Well consider the patent on rotation. A japanese company recently
claimed that most of the AES finalist violate their patent. So
what is their patent ? Using rotation in encryption !!! [...]
I would like to point out to all thos
Cryptography-Digest Digest #717
Cryptography-Digest Digest #717, Volume #11 Sat, 6 May 00 13:13:01 EDT
Contents:
Re: GPS encryption turned off ([EMAIL PROTECTED])
Re: Increasing bit Entropy (Francois Grieu)
Re: Increasing bit Entropy (Francois Grieu)
Re: Fresco transmits my name (was: Spammed after just visiting a site) (Mark Wooding)
SBOX page (Tom St Denis)
Re: Crypto Export (David A Molnar)
SecureDoc 2.0-Does anyone have any experience with it? ([EMAIL PROTECTED])
Re: Crypto Export (Jerry Park)
Re: SecureDoc 2.0-Does anyone have any experience with it? (Tom St Denis)
Re: Increasing bit Entropy (Tim Tyler)
Re: Fresco transmits my name (was: Spammed after just visiting a site) (Greg
Hennessy)
Re: Any good attorneys? ("Trevor L. Jackson, III")
Re: Unbreakable Superencipherment Rounds (John Savard)
Re: GPS encryption turned off ("Trevor L. Jackson, III")
From: [EMAIL PROTECTED]
Crossposted-To: sci.geo.satellite-nav
Subject: Re: GPS encryption turned off
Date: Sat, 06 May 2000 13:20:02 GMT
In article [EMAIL PROTECTED],
[EMAIL PROTECTED] wrote:
Mxsmanic wrote:
"Martin Grossman" [EMAIL PROTECTED] wrote in message
news:[EMAIL PROTECTED]...
SO, since the PLGR is considered not classified
(I highly doubt this statement) ...
If the device itself is classified, then anyone using it or coming
into
contact with it must have an appropriate clearance. That might
unacceptably restrict the number of people able to use the device
in the
field.
Your right...I forgot about that!
BUT..remember! there is a difference between
not classified and unclassified
not classified means its never been reviewed by Dod
and
unclassified means its has been reviewed and has not been classified
confidential/secret/top secret or it means it was classified at one
point
in time and is now unclassified (available to the general public).
The DoD performs an extensive security review of PPS receivers. PLGRs
have passed the review and are considered Unclassified. Unlcassified
DOES NOT mean available to the general public. PLGRs are Unclassified,
but are not available to the general public
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: Francois Grieu [EMAIL PROTECTED]
Subject: Re: Increasing bit Entropy
Date: Sat, 06 May 2000 15:46:18 +0200
RavingCow [EMAIL PROTECTED] wrote:
If I have two streams of bits with a entropy of 0.5 bits / bit,
how can I combine these to increase randomness ?
Obviously, XOR would not be a good choice, but would
addition mod. 2 work?
XOR indeed is addition mod 2.
Would the entropy go up to 0.75, or would it be less ?
Assuming all bits are independant, the XOR of the bit streams
will have entropy
0.?135367285659782517112711.. bits / bit
Note: one digit intentionaly changed to ? in the above, to preserve
the interest of the exercice.
Hint: a bit stream of independant bits set with probability p
has entropy -p*lg2(p)-(1-p)*lg2(1-p)
Assuming both bitstreams are biased towards 0, the OR of the
bitstreams will have entropy
0.?375451476446613474988052.. bits / bit
where ? is the same digit as above.
Fun: design a combiner with memory that outputs at the same rate
as the OR above, but with entropy closer to 1.
More difficult: discuss what happens if the bitstreams are
correlated.
Francois Grieu
--
From: Francois Grieu [EMAIL PROTECTED]
Subject: Re: Increasing bit Entropy
Date: Sat, 06 May 2000 15:56:01 +0200
RavingCow [EMAIL PROTECTED] wrote:
If I have two streams of bits with a entropy of 0.5 bits / bit,
how can I combine these to increase randomness ?
Obviously, XOR would not be a good choice, but would
addition mod. 2 work?
[earlier spoiler removed as per David Blackman's suggestion]
Would the entropy go up to 0.75, or would it be less ?
Assuming all bits are independant, the XOR of the bit streams
will have entropy
0.?135367285659782517112711.. bits / bit
Note: one digit intentionaly changed to ? in the above, to preserve
the interest of the exercice.
Hint: a bit stream of independant bits set with probability p
has entropy -p*lg2(p)-(1-p)*lg2(1-p)
Assuming both bitstreams are biased towards 0, the OR of the
bitstreams will have entropy
0.?375451476446613474988052.. bits / bit
where ? is the same digit as above.
Fun: design a combiner with memory that outputs at the same rate
as the OR above, but with entropy closer to 1.
More difficult: discuss what happens if the bitstreams are
correlated.
Francois Grieu
--
From: [EMAIL PROTECTED] (Mark Wooding)
Crossposted-To: comp.sys.acorn.misc
Subject: Re: Fresco transmits my name (was: Spammed after just visiting a site)
Date: 6 May 2000 14:05:33 GMT
[sci.crypt added to newsgroups.]
greg [EMAIL PROTECTED] wrote:
"Rev. James Cort" [EMAIL PROTEC
Cryptography-Digest Digest #717
Cryptography-Digest Digest #717, Volume #10 Fri, 10 Dec 99 10:13:01 EST
Contents:
Re: symmetric encryption based on integer factoring (Tom St Denis)
Re: Synchronised random number generation for one-time pads (Guy Macon)
Re: Synchronised random number generation for one-time pads (Guy Macon)
Re: Synchronised random number generation for one-time pads (Guy Macon)
Re: symmetric encryption based on integer factoring ([EMAIL PROTECTED])
Re: weak algorithm, too hard for me (Guy Macon)
Re: If you're in Australia, the government has the ability to modify ("Trevor
Jackson, III")
Re: Digitally signing an article in a paper journal ("Trevor Jackson, III")
Re: Synchronised random number generation for one-time pads ("Trevor Jackson, III")
Re: Random Noise Encryption Buffs (Look Here) ("Trevor Jackson, III")
From: Tom St Denis [EMAIL PROTECTED]
Subject: Re: symmetric encryption based on integer factoring
Date: Fri, 10 Dec 1999 13:00:06 GMT
In article 82q3tn$s27$[EMAIL PROTECTED],
Scott Fluhrer [EMAIL PROTECTED] wrote:
This problem appears to have nothing to do with "factoring". It's
strength, if any, looks like it be closer to the discrete log problem.
Also, the multiplicative inverse of a generator is always a generator,
so there's no need to specify it directly.
Oh ok.
Well, lets make a preliminary analysis of it. I assume that g and p
are
publicly known parameters. Since you do not describe how x is
generated,
let us assume that all possible values of 0 = x p-1 are equally
probable.
Then, we immediately note that all values of g^x from 1 = g^x p are
equally probable, since because g is a generator, there is a one-to-
one
mapping between the two. So, your system could be simplified to:
C = (P * y) mod p
P = (C * y^-1) mod p
Where all values 1 = y p are possible. Next, we note that, for any
possible pair P, C, there is a unique y s.t.
C = (P * y) mod p.
In other words, for any C, for each possible plaintext P, there is a
key that will decrypt it to that plaintext. This implies that this
system is essentially an OTP, except it's a lot harder to evaluate.
And so, *all* the strength of the system is in how you generate x.
Yes and no. There is a reason why I chose g^x mod p, instead of just x.
Essentially. Assume the attacker has the plaintext/ciphertext for the
first message. Then, he can compute:
g**X = C * P**-1 mod p
Then, given the nth ciphertext Cn, he can compute
Pn = Cn * (g**X)**-n
= Cn * (g**-nX)
I believe any linear method of assigning x's will have the same
problem.
That's what I thought. Originally I said why not just increment x mod
p-1. But I then proceded to break it ... :)
Just an idea :)
BTW: why do you think that this is even slightly practical? You
require
a full modular exponentiation for every single message. You can run
RSA just as fast.
It's not, but I am toying with number theory. They don't teach it in
school so I have to work it out myself, and ask here once in a while.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
--
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Synchronised random number generation for one-time pads
Date: 10 Dec 1999 08:17:09 EST
In article [EMAIL PROTECTED], [EMAIL PROTECTED] (Tim Tyler) wrote:
OTPs are generally quite secure against eavsdroppers who don't know the
message they contain. They're useless against simple complete
known-plaintext attacks.
It depends on what you mean by "useless". I would say that being able
to send other plaintexts without the attacker being able to decode
them is quite usefull, wouldn't you? The known-plaintext attack
described does allow interception and substitution, which is another
way of saying that an OTP has limited value as a digital signature.
The known-plaintext attack never allows the attacker to do anything
with a message other than his known-plaintext message. That's useful.
--
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: Synchronised random number generation for one-time pads
Date: 10 Dec 1999 08:25:41 EST
In article 82pet6$cob$[EMAIL PROTECTED], [EMAIL PROTECTED]
(Charles Meigh) wrote:
Thanks everyone, I hadn't come across the problem of interception and
forgery yet. I think I'll add a decent physics textbook to my shopping
list as well as cryptology. I'm still thinking that there might be some
vastly wide choice of 'celestial' events that could produce truly random
numbers that will still be sufficiently similar observed from any two (or
more) points on the globe, which would make OTP use more economical.
You have that already. Just generate your random numbers using whatever
method you prefer and post them in a newsgroup. Or you can put them on
a CD and sell the CD on a web site. Or broadca
