Cryptography-Digest Digest #537, Volume #13 Wed, 24 Jan 01 02:13:00 EST
Contents:
Re: Fitting Dynamic Transposition into a Binary World (Kenneth Almquist)
Re: TSEPRNG, a secure RNG ? (Bryan Mongeau)
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
Re: Dynamic Transposition Revisited (long) (Terry Ritter)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Kenneth Almquist)
Subject: Re: Fitting Dynamic Transposition into a Binary World
Date: 24 Jan 2001 05:41:18 GMT
[EMAIL PROTECTED] (John Savard) wrote:
> 2^160 equals
> 1461501637330902918203684832716283019655932542976
>
> and the number of 164-bit balanced strings is
> 1454706556296192477283016662986999417820887445240
>
> so one way to use Dynamic Transposition on arbitrary binary sequences
> would be to have a coding for 160-bit arbitrary sequences into 164-bit
> balanced sequences.
>
> Some sequences of 160 bits wouldn't have an equivalent, and so would
> have to be converted to something else; either to shorter balanced
> sequences, which could also be enciphered by Dynamic Transposition, or
> to some other kind of object to be enciphered in another way.
This means that your encoding is effectively variable length. For each
160-bit sequence, you need to transmit an indication of whether it
has been encoded as a 164-bit balanced sequence, or some other way.
This wastes communication bandwidth (though not a lot) and also
complicates the encoding because the indication cannot be transmitted
in the clear (or you leak information). Might I suggest coding 158-bit
arbitrary sequences as 162-bit balanced sequences?
There number of 162-bit balanced sequences is
365907784099042279561985786395502921046971688680
while 2^158 is slightly less:
365375409332725729550921208179070754913983135744
This would create a fixed overhead of four additional bits for every
158-bit block, which would add a communication overhead of about 2.53%.
If you decided to use a block size of 128 bits (in order to interface
to standard 32 and 64 bit hardware more easily), adding four bits per
block amounts to a communication overhead of 3.125%, which is still
quite reasonable.
> Of course, this kind of begs the question of how to devise an
> efficient coding for arbitrary strings into balanced strings. From
> arbitrary binary strings, one could use a simple numeration of
> balanced strings...
>
> 00000000 = 0000011111
> 00000001 = 0000101111
> 00000010 = 0000110111
> 00000011 = 0000111011
> ...
> 11111011 = 1111100000
> 11111100 ... coded to something else
>
> and maybe there *might* be a simple algorithm to do this for strings
> too large to put in a table
Finding an algorithm to do this is an interesting challenge.
The arbitrary strings can be regarded as binary numbers. We define
a mapping between balanced strings and numbers by listing the
balanced strings in lexical order and numbering them starting from
zero, as you have done above.
The first thing to note is that we can compute the number of balanced
strings with a given prefix relatively efficiently. For example,
let's say that our balanced strings are 162 bits long, meaning they
contain 81 "1" bits and 81 "0" bits. If we want to know how many
strings have the prefix "110", we count the number of zeros and ones
in the prefix. There are two "1" bits and one "0" bits. This means
that the remainder of the string must have 79 "1" bits and 80 "0"
bits. The number of possibilities is (79+80)! / (79! * 80!).
This allows us to process a balanced string from left to right,
keeping track of the number of the first (or last) balanced string
beginning with the bits we have seen so far. This minimum starts
out as zero. As we scan the string, if the next bit is zero, then
the minimum is unchanged. If we encounter a one, then we know that
all the balanced strings which have a zero where the string we are
scanning has a one must lexically precede the string we are scanning.
Therefore, we add the number of such strings to the minimum.
To compute the number of a balanced string, we perform the operation
described in the preceding paragraph, counting the number of "0" and
"1" bits as we go along. When we have seen 81 of either type of bit,
then there is only one possible value for the remaining bits. (They
must be all zeros or all ones.) At that point there is only one
balanced string beginning with the bits we have seen so far, and
we know what the number of that balanced string is, so we are done.
To generate the balanced string corresponding to a number, we modify
the algorithm to generate bits rather than reading them. At each
step, we first try outputting a "1" bit. If that would make the
minimum exceed the number whose bit string we are trying to construct,
(or if we have already output 81 "1" bits) we output a "0" instead.
These algorithms can be executed moderately efficiently. The
combinatorial calculation used to determine the number of balanced
strings with a given prefix can be precomputed and stored in a
table. At the cost of using larger tables, we could make the
decoding algorithm process multiple bits of the balanced string
at a time. However, there is no obvious way to generate a balanced
string without doing one bit at a time.
Kenneth Almquist
------------------------------
From: Bryan Mongeau <[EMAIL PROTECTED]>
Subject: Re: TSEPRNG, a secure RNG ?
Date: Wed, 24 Jan 2001 06:22:45 GMT
Splaat23 wrote:
> Yes, similar things have been done. "TrueRand" is think is one where
> differences between multiple timers in the system is used for entropy.
> As with many things, these can potentially be controlled by an attacker
> and should be used with other forms of entropy.
>
> - Andrew
I thought truerand (the one used in PGP at least) measures the timing
between keystrokes...
Could you elaborate a little on how an attacker might be able to "control"
the entropy created by repeated race conditions?
--
<==================================>
Bryan Mongeau
Lead Developer, Director
eEvolved Real-Time Technologies Inc.
www.eevolved.com
<==================================>
"I know not with what weapons World War III will be fought, but World War
IV will be fought with sticks and stones."-- Einstein
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Wed, 24 Jan 2001 06:37:41 GMT
On Wed, 24 Jan 2001 02:24:00 GMT, in <94lebq$2gj$[EMAIL PROTECTED]>, in
sci.crypt AllanW <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Terry Ritter) wrote:
>> When I think of Dynamic Transposition, I think of 512-byte / 4096-bit
>> blocks. This stuff scales almost linearly, and 512 bytes is just a
>> small buffer.
>>
>> I suspect that if we run the numbers, some modest minimum size --
>> perhaps 128 bits / 16 bytes -- is required for serious strength. We
>> can scale it down to look at, of course, but we can't expect strength
>> there as well.
>
>Really? I think your original paper made a good case for
>allowing short block sizes. Although the 4-byte block
>seems to be stretching things too far, a 16-byte block
>would work well.
Which is what I just suggested.
>In degenerate cases such as all 0's,
>this would allow 7 bytes of data followed by 9 bytes of
>filler. For typical ASCII data this would allow 10 bytes
>of data and 6 bytes of filler. For data that's already
>balanced or very nearly so, we could put 15 bytes of
>data into a 16-byte block.
Right.
>Larger block sizes would help to make the overhead
>smaller, though.
Right.
>The best case will always require 1 byte
>of filler,
Right.
>while the worst case will always require N/2+1
>bytes of filler (for N-byte blocks).
Looks right.
>As I understood the filler bits to work, the data would
>look like this before the transposition begins: if the
>data had more 0-bits than 1-bits, it would take the form
> XX....XX 00..00 11..11
>where X bits represent the data, and then there are 1-8
>0-bits followed by 1 or more 1-bits. If the data has
>more 1-bits than 0-bits, simply reverse the filler:
> XX....XX 11..11 00..00
>this time using 1-8 1-bits and then 1 or more 0-bits.
That does not seem to be the way I did it.
I don't understand having both 0's and 1's balancing bytes. If we
have an excess of 0's, we want any full balancing bytes to be all 1's,
with the mixed byte being what it needs to be. Since the mixed byte
must be mixed to be a flag, it cannot balance a full 8 bits, but at
most 6 (1000 0000 is an excess of 6 0's).
>Another way to say this is to show what the filler
>would look like for various imbalances. Here I'll
>assume that the data has more 0-bits than 1-bits; use
>the complement if the opposite is true.
>
> If there are B more 0-bits than 1-bits, then the
> filler looks like (in hex):
>
> B=0 0F
> B=2 1F
> B=4 3F
> B=6 7F
> B=8 0FFF
> B=10. 1FFF
> B=12. 3FFF
> B=14. 7FFF
> B=16. 0FFFFF
> B=18. 1FFFFF
> B=20. 3FFFFF
> B=22. 7FFFFF
> B=24. 0FFFFFFF
> ...and so on.
Looks right.
>(Note that the number of data bits is always divisible
>by 8 and therefore an even number. This means that the
>number of 0-bits, minus the number of 1-bits, must also
>be an even number.)
Right.
In a fixed-size array of bits, changing a '1' to a '0' is to decrease
the 1's-count by 1, and increase the 0's-count by 1, a difference of
2.
>In the worst case for a 16-byte (128-bit) block, the
>data would be 56 0-bits. Then the program would add 8
>more 0-bits and 64 1-bits.
>
>In the obvious best case, the data has 60 0-bits and
>60 1-bits in any order. Then the filler is 0F -- 4
>0-bits and 4 1-bits. The best case (15 bytes in a
>16-byte block) is also achieved when there are up to
>6 more 1-bits than 0-bits or vice-versa -- the filler
>still fits in one byte.
Right. Thus the advantage of this particular balancing scheme: The
flag byte is not wasted (or even counter-productive), but instead can
participate in balancing.
>If there is any weakness at all to this scheme, it's
>that even though you're using a fixed-size block, you
>cannot predict in advance how many blocks the message
>will need because each block contains between N/2-1 and
>N-1 bytes of data.
Yes, but I think that's a strange thing to do anyway. Why would we
predict the size in advance, when we obviously will traverse it soon?
One might, I guess, allocate a buffer to hold the whole thing, but an
alternative is to allocate big enough chunks as needed to make the
allocation computation a nit.
>On the other hand, this could be
>considered a strength because of the flip side of this
>observation: once you know how long the ciphertext is,
>you can calculate how many fixed-size blocks were used,
>but this does not tell you how long the original
>plaintext was. The larger the blocksize, the more true
>this is.
Yes, I think so.
>Other than that, if there's any reason why a 16-byte
>block is less secure than a 512-byte block, it sure
>isn't obvious to me! (For whatever that's worth)
Right now, I don't see the issue as security.
My main reason for using a large block would be to minimize balancing
overhead, which would here be 1 byte in 16, or over 6 percent,
minimum. Even 5 balancing bytes out of 512 would be under 1 percent.
Also the larger block tends to reduce relative variation in balance,
which is especially useful with random-like data.
Another reason might be to reduce OS overhead in manipulating data.
We certainly don't want to be asking the OS for 16-byte blocks, but of
course we might well have a tight local buffering system.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Wed, 24 Jan 2001 06:37:55 GMT
On Wed, 24 Jan 2001 03:31:28 GMT, in
<k0sb6.111177$[EMAIL PROTECTED]>, in sci.crypt "Matt
Timmermans" <[EMAIL PROTECTED]> wrote:
>"Terry Ritter" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> Assume the supposedly "random" pad you have is in fact predictable.
>> Surely you will not argue that a "OTP" with a completely predictable
>> sequence is secure. But wait! Isn't the OTP *proven* secure?
>
>The pad is defined to be random. If it's not random, then your're not using
>OTP. Whatever cipher you _are_ using may very well be insecure.
That's the part that is too cute for me: You can say you have an OTP,
so users think they have "mathematically proven" security, and then,
later, if we find out that the pad really is predictable, you announce
that the damage really was not due to the OTP after all.
So the damage is not accounted to the OTP, despite the fact that it
failed in use. That seems like slimy cryptography to me. The whole
point of having a name for a cipher is to be able to associate a
design with an outcome, not wiggle out of responsibility.
It may be that absolutely random pads do exist. But since we cannot
measure the predictability of those, if we cannot somehow prove they
are not predictable, we can only assert security, not prove it.
>> For proven OTP security it is not sufficient simply to use the
>> sequence only once. It is *also* necessary for the sequence to be
>> "random," or more explicitly, "unpredictable."
>
>Yes. That's how OTP is defined.
>
>> The problem with this requirement is that we cannot measure an
>> arbitrary sequence and thus know how unpredictable it is.
>
>You also cannot measure a Rijndael key to find out whether or not it is
>known to other parties -- you don't use arbitrary sequences as keys.
We are discussing a security proof. If you want a security proof, you
need to prove the assumptions. If OTP assumes a random pad, then you
need to be able to prove that pad is random. In reality, we cannot
measure such a thing, and probably cannot prove it.
>> Nor can we
>> assemble all sorts of measurements of radioactive events or other
>> random sources with the guaranteed assurance of unpredictability that
>> proof requires. That does not mean that most sequences we develop
>> will not be very strong, what it means is that we cannot prove it.
>
>Sure you can. You can collect a large amount of biased random data by
>sampling natural phenomena, use IDA to divide it into many small chunks,
>take one, and throw the rest away. Repeat until you have enough. The only
>difficult part is making sure you underestimate the entropy of your
>source -- and even that's not too hard. With certain types of natural
>phenomena, you can even base a proof of unpredictability on the uncertainty
>principle.
It may be possible to have equipment which has a pretty decent proof
of strength. In reality, quantum events are fairly small, and sensing
them typically requires some electronics. That means the electronics
can go bad, or oscillate, or have a noisy connection, or work
intermittently, or whatever. Your task is to prove absolutely beyond
any shadow of a doubt that nothing like that happened.
I am very familiar with electrical noise, and I have promoted sampling
a source which has a known non-flat distribution. Then, if we get the
expected distribution, we may leap to the conclusion that everything
has worked OK. However, since there can be no test for abstract
randomness, it is extremely difficult to make the leap to
cryptographic levels of assurance. Any number of subtle things might
happen which might not be detected, and yet would still influence the
outcome. We can be very sure, but is that really mathematical proof?
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Wed, 24 Jan 2001 06:38:10 GMT
On Tue, 23 Jan 2001 23:37:26 GMT, in
<[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] (John Savard) wrote:
>On Tue, 23 Jan 2001 22:12:41 GMT, [EMAIL PROTECTED] (Terry Ritter) wrote,
>in part:
>
>>All of which is not a problem, because the actual permutation which
>>encrypted the data is hidden in that clump. There is no information
>>to distinguish the correct one.
>
>>You might as well say there is a problem because one could read the
>>RNG state and thus know the keying of the cipher. We assume that
>>state is kept secure.
>
>>There is no way to distinguish the correct permutation from the huge
>>group which can generate the same transformation. And it is only the
>>correct permutation which leads back (eventually) to the shuffling
>>sequence.
>
>>A weakness which cannot be exploited is no weakness at all.
>
>But in what way does that differ from me saying that - if I propose a
>cipher which consists of four rounds of DES, with subkeys supplied by
>some form of stream cipher generator - that given a corresponding
>plaintext and ciphertext after two rounds,
I am not psychic. I can't address whatever vision of a design you
have, unless you describe it in detail. If you want me to address how
these ciphers differ, you will simply have to describe your design in
at least as much detail as I did in my "Revisited" article. Only then
can one hope to draw out distinctions and conclusions.
>there are 2^32 different subkey pairs which could have produced that
>particular output from the given input? (because of the expansion
>permutation and the way the S-boxes in DES work)
>
>If _you_ are going to complain that DES isn't a good starting point to
>work from, because it can't produce all (2^64)! mappings between
>inputs and outputs, so it's not a "true general substitution", then I
>don't see why I shouldn't point out that Dynamic Transposition is also
>not a true general substitution of bit-balanced blocks.
Because the comparison is incorrect.
The ciphering part of DES is an emulated huge substitution. Yet
keying can create only a tiny fraction of the possible substitutions
of that size.
The ciphering part of Dynamic Transposition is actual permutation.
Any possible permutation can be selected by the keying.
The distinction you have been pointing out is at the next level,
beyond the permutation, beyond the ciphering, and so beyond the direct
comparison with DES.
>Ah, but it's a transposition, and it is a "true general
>transposition", you seem to have said. I'm pointing out that this is
>something that really doesn't matter;
It does matter.
To be comparable, you would need to describe a "Dynamic DES" that not
only changed keying on a block-by-block basis, but also allowed keying
to select among every possible huge substitution. And I don't think
we know how to do that.
With that Dynamic DES design, it would no more be possible for Dynamic
DES to select every possible sequence of substitutions than for
Dynamic Transposition to select every possible sequence of
permutations.
But even with that Dynamic DES design, known plaintext would
completely reveal which transformation was used for that block. But
with Dynamic Transposition, known plaintext would not reveal even one
bit movement, let alone the entire permutation.
>if it's a limitation for one
>case, it's a limitation for the other case as well, that the total
>overall relation of possible inputs to possible outputs is limited.
I have no problem making a fair comparison, but you insist on
fastening on a "weakness" which is already two steps away from DES,
and beyond anything I can imagine creating from DES.
I don't think we know how to emulate any possible permutation with
flat probability. In contrast, we do know how to create any possible
permutation with flat probability. That is part of the advantage.
>Essentially, the fact that "transposition" is used as the name for a
>class of ciphers considered distinct from substitution - while "XOR",
>or "monalphabetic substitution" are considered forms of substitution -
>is leading you into a fallacy based on regarding accidental historical
>linguistic habits as somehow fundamental.
The argument is not semantic. If you think it is, you have missed it.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Wed, 24 Jan 2001 06:38:41 GMT
On Wed, 24 Jan 2001 03:00:42 GMT, in <94lggn$451$[EMAIL PROTECTED]>, in
sci.crypt AllanW <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Terry Ritter) wrote:
>> Dynamic Transposition is unusual in that knowing the plaintext and the
>> associated ciphertext does not reveal the enciphering permutation.
>> The reason for this is that many different bit-permutations will
>> produce the bit-for-bit exact same transformation between plaintext
>> and ciphertext. Therefore, having known plaintext does not reveal the
>> enciphering permutation, and thus cannot be exploited to begin to
>> expose the RNG sequence.
>>
>> Note that even if the correct permutation were found, the RNG sequence
>> which created it would not be exposed to any extent, if
>> double-shuffling was used to create the permutation. The reason for
>> this is that double-shuffling would use twice the amount of RNG
>> sequence as needed for a selection among all possible permutations.
>> Double-shuffling is literally an arbitrary permutation from a known
>> state, and then another arbitrary permutation from that to any
>> possible permutation. Any particular result permutation could be the
>> result of any possible first permutation, with the appropriate second
>> permutation, or vise versa. Accordingly, one knows no more about what
>> sequence was involved than before one knew the correct permutation.
>
>Consider this alternative to double-shuffling (or they could be
>used together): Process the entire plaintext once using an
>N-byte block. But instead of considering the output to be
>ciphertext, pack it into blocks of M-bytes, where M is less than
>N/3, and mutually prime to N. For instance, N=2187, M=512. Once
>again, use filler bits so that the number of 0-bits and 1-bits
>are balanced, and then shuffle that buffer. I haven't thought
>this through all the way yet; you might have to use two PRNG's in
>order to be able to decrypt the numbers later, but if we can find
>a way to know which PRNG values are used for which decoder (i.e
>first N for the first buffer, then 3M for the second buffer, and
>then N more for the big one and so on), then a single PRNG might
>still suffice. The smaller buffer will need slightly more values
>than the big one, due to adding a very few bytes to each buffer
>to balance 0-bits with 1-bits.
>
>The point of using double-shuffling is to make known-plaintext
>attacks more difficult by further masking the actions of the
>PRNG.
Yes, sort of.
Of course, to get there, we must first assume that the opponent has
fully defined an enciphering permutation, and we have no idea how one
might do that. That is primary strength.
The double-shuffling is just closing another door, and has probably
wasted far more discussion than it is worth.
>But you also acknowledged that the result of two rounds
>of shuffling is equivalent to one round controlled by some
>other unknown sequence of random numbers.
Well, of course. That's what "hiding" implies.
Double-shuffling is analogous to a hash, which is non-reversible
specifically because more information is processed than can be
represented in the internal state. As a consequence, many different
sequences can produce the same result, so even if we know that result,
we don't know which sequence produced it.
Double-shuffling produces a permutation, a permutation which might
have been produced by a single shuffle. But if we create the
permutation with a single shuffle, to know the permutation is to know
the sequence.
Instead, since we create the permutation from twice the amount of
information needed for a permutation, to know the permutation is *not*
to know the sequence.
>On the other hand,
>using two buffers of different sizes makes the two passes have
>different meaning. Also, in order to know that you're using
>PRNG values that will succeed, you will have to decode at least
>4 of the smaller blocks in order to have enough data to feed
>into the larger block. Using two different PRNG's might make
>analysis even more difficult.
Right. We can pile this stuff up as high as we want. But exactly
what are we solving?
If there is a weakness, we need to solve it. But there is no point in
doing things at random.
The main strength of Dynamic Transposition is that the opponent's
cannot define what permutation has occurred, even if they have both
the plaintext and the ciphertext.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
