Re: Initializing GFSR Generators.

From: Terry Ritter (ritter@ciphersbyritter.com)
Date: 02/23/03


From: ritter@ciphersbyritter.com (Terry Ritter)
Date: 22 Feb 2003 17:56:31 -0800

cybervagrant@yahoo.com (Cyber Vagrant) wrote in message news:<9f8a576b.0302221045.3697df81@posting.google.com>...
> I have already, good site :) Your appoach make sense to me. But you
> created Cloak some 10 years or more ago, what I'm wondering is how
> would it stand up to Uncle Sam's present day crew, who can reportedly
> crack a 40bit key (of a known cipher!!!) in 0.1 seconds.

GOVERNMENT ABILITIES

Since we have no information about what the government
guys can do, we cannot know. Anything beyond that is
just speculation, perhaps informed by what information
we do have.

Trying to keep something from the government when they
want to see it probably is a loosing proposition anyway.
An actual technical break is perhaps the most unlikely
of the many ways in which government guys can expose
information.

KEY MANAGEMENT

It is important to see the system around "the cipher"
(i.e., the "cipher system") as a significant part of
security. Key-management is an ever-present issue.
Note that only an uncertified public key can support
a continuous man-in-the-middle attack without having
to break any cipher at all.

I innovated an "alias file" to hold the actual keys,
which could thus be long and random. The user needed
to remember a keyphrase to enable the system to search
through the alias file for a particular alias. When
that alias was found, the associated key would be used,
but the user never saw those keys.

One thing I did which I regard as particularly cute
was to implement the alias file encryption such that
keys could be added by concatenation as *ciphertext*.
That is, a new key would be created and enciphered,
and then could be added to the alias file by a
simple file copy. That minimized the need to expose
either the key or the alias file and made secret-key
transport more reasonable.

In my alias file implementation, each key had a starting
date. By adding new keys to the start of the file,
and then searching from the front, the system automatically
used the new keys when their date was reached, which
provided an easy way for an office to change keys
periodically, without involving the users. Also,
messages could be archived as ciphertext and then
deciphered under the old keys as selected by alias
and date.

CLOAK2 STRENGTH

The Cloak2 cipher itself has some "strength in depth."
To break it, somebody has to get through a combiner
composed of a sequence of two levels of keyed Dynamic
Substitution, with the second level being a byte-by-byte
selection among 16 different tables. The table contents
are not constant but instead change. I am not aware
that anybody has even the beginning of a good handle
on how to get through that.

The other aspect of Cloak2 strength is the RNG. That
is a huge-state Additive RNG (as opposed to a GFSR),
which eliminates the need for special initialization,
and thus provides for more general keying. The main
remaining problem, of course, is the linear structure
or correlation in the resulting sequence, which I break
up with a jitterizer.

I have personally reconstructed the internal state of
some RNG's, and doing that through a jitterizer seems
very tough to me. The way correlation is typically used
in an attack is to be able to relate values at known
relative sequence positions, but the jitterizer changes
both value and adjacency.

In any case, many email messages are actually smaller
than the RNG state anyway, making such reconstruction
actually impossible from the ciphertext side. And
since the keying side is 992-bits wide, it is hard
to see how anyone could get a toe-hold there.

 
> What I have presently in mind is similar, but incorporates more
> dynamic operations, like the jitterizer. Particularly, I use more
> than one generator say three and dynamically switch between them then
> give the resulting output a little more attention.

I see switching between generators as a form of
combining, and one example of that is the Geffe combiner,
which is known to be insecure. Creating good combiners
is very, very tricky, because of balance and correlation
problems. As soon as you allow correlation in the combiner,
an attacker can essentially bypass the combiner by using
more data.

One alternative I have considered but never gotten a
good analytical handle on is to have multiple feedback
polys, and then to change those dynamically during
operation. That generality would be slower, especially
with 9-nomials instead of trinomials, but it should
give a sequence with different forms of correlation
as it progresses. Unfortunately, it also negates the
theory which guarantees long cycle length, and I have
never been happy with that *and* the slower speed.

 
> I like the multiple S-boxes, I have already implemented a design,
> proposed by somebody else, of 256 x 1 byte S-boxes that use the hashed
> value of some previously encrypted values to select the next S-box.
>
> I used a 32bit generator to initialize the boxes by bitting off 8bits
> at a time from one 32bit result, then checking the value to see if it
> was already used and discarding if it was.
>
> I think your shuffling method would be faster.

Almost certainly. Keying s-boxes efficiently is a
solved problem if we have a keyed RNG.

 
> What I'm considering now is, since there are 256! permutations of 256
> unique bytes thats something in the order of 10^508, and since
> computeres these days are better, faster, stronger than they were
> before, to using a newly generated table for each subsitution. Do you
> think that would reduce the need to add diffusion to the process?

Diffusion per se is not necessary in stream ciphers.
That is a characteristic of s-boxes and the emulated
huge s-boxes we call conventional block ciphers.
Because that model inherently has diffusion, diffusion
must somehow be created and supplied. Stream ciphers
are a different model, and may or may not have
diffusion as desired.

Probably a better way to think about the strength of
an s-box is to note that an 8-bit table only has 256
entries. If there is any input/output exposure at all,
it does not take long before the whole table is exposed
and, thus, useless. So the issue becomes that of
protecting the table, and ensuring that no entry is ever
exposed. Creating new tables for every enciphered byte
is probably unreasonable. Creating new tables whenever
an entry is re-used is possible, but still has very
high overhead.

---
Terry Ritter     http://www.ciphersbyritter.com/
Crypto Glossary  http://www.ciphersbyritter.com/GLOSSARY.HTM


Relevant Pages

  • Re: =?windows-1252?Q?The_Renaissance_is_Here_=96_SD_cryptography=2E?=
    ... cipher in itself. ... alphabet later to create keys ad hoc, ... All modern cryptography depends on going public with the vitally ... Even RSA and other public-key algorithms do not ...
    (sci.crypt)
  • Re: Im still amused.
    ... keys with certain algorithms. ... independent operation to the encryption algorithm that will use it. ... cipher whenever you wish to call it. ... Reference: "Theoretically Unbrakable Cryptography" ...
    (sci.crypt)
  • Re: Is encrypting twice much more secure?
    ... so if one pass is secure enough you're okay. ... Wouldn't an 'definition' of 'statistically independent keys' (not very ... imply that the 2nd cipher couldn't weaken the work of the ... Consider a block cipher as a set of permutations of plaintext into ...
    (sci.crypt)
  • Re: Is there a Mathematician Cryptographr in the House.
    ... N must divide Sum just once and leave the residue (Mod ... This is the algorithm that produces two sets of random keys in the ... following cipher in modular arithmetic. ... designed the OTP in conjunction with his contemporary Gilbert Vernam. ...
    (sci.crypt)
  • Re: Is there a Mathematician Cryptographr in the House.
    ... N must divide Sum just once and leave the residue (Mod ... This is the algorithm that produces two sets of random keys in the ... following cipher in modular arithmetic. ... understanding of even basic cryptography. ...
    (sci.crypt)