Cryptography-Digest Digest #496, Volume #13 Fri, 19 Jan 01 04:13:01 EST
Contents:
Re: Dynamic Transposition Revisited (long) (Benjamin Goldberg)
Re: Dynamic Transposition Revisited (long) (Benjamin Goldberg)
Re: block algorithm on variable length without padding?
([EMAIL PROTECTED])
Re: Why Microsoft's Product Activation Stinks (Arturo)
Hierocrypt-L1 (Pascal Junod)
Re: Kooks (was: NSA and Linux Security) (John Savard)
Re: Dynamic Transposition Revisited (long) (John Savard)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 19 Jan 2001 06:26:38 GMT
John Savard wrote:
>
> On Fri, 19 Jan 2001 03:41:40 GMT, Benjamin Goldberg
> <[EMAIL PROTECTED]> wrote, in part:
>
> >You seem to be ignoring that before shuffling, the data is
> >accumulated into bit-balanced blocks. Did you read the whole paper?
>
> I admit that I only skimmed through it. I saw the word 'bit-balanced',
> but didn't look closely.
>
> Upon looking again, I see that he indeed explicitly mentioned this
> point. However, I note that details of bit-balancing were not given.
> If the data is *not* pre-processed or compressed or whatever, and if
> the point at which a block is cut off depends on what bits are in the
> block (and the extent of the need for balancing) then that has to be
> indicated somehow, and the indications need to be encrypted...
Not quite. Let's assume that we are using 128 bit blocks. The front of
the block contains data, the end of the block contains balancing bits.
If the balancing bits are all 1s, then all 0s (or vice versa), and we
fill in as many bytes of data as we can into the front of the block,
only one of the balancing bytes will contain both ones and zeros, and
that will be the first balancing byte. All of the rest of the balancing
bytes, from there to the end of the file, will contain all ones, or all
zeros.
No external data is needed to indicate where the balancing bytes begin.
>
> this could get quite messy.
>
> Of course, a *simple* way of dealing with this problem would be to
> code 6 bits of binary input to an 8-bit byte in a 4 of 8 code, using
> 64 of the 70 possible values. This would be a brute-force approach,
> but it would mean that one would not have a data-dependent concern
> with the block lengths. They could be uniform, or chosen randomly.
Huh? I don't get what you're saying.
> I suppose even with a substitution phase, if one ensures bit balance,
> the transposition phase is made maximally strong; but _then_ one has a
> redundancy problem (since after transposition, any simplistic scheme
> of ensuring bit balance wouldn't be preserved - i.e. after a bit
> transpose of bytes in a 4 of 8 code, each byte of the result would not
> necessarily have exactly four 1 bits).
We have a nice big 128 bit block. We shuffle all the bits in it. We
are not shuffling the bytes in it. If bits were balanced before
shuffling the bits, they will certainly be balanced after we shuffle the
bits.
[snip]
> Of course, the initial means of achieving bit-balance needn't be as
> inefficient as a 4 of 8 code, but it still *won't* be fully optimal
> over the entire transposition block length. Whatever means of
> obtaining bit-balance is used, it will need a smaller "window" than a
> whole transposition block to be reasonably efficient.
bal = (# bits in block) / 2
while( (unfilled bytes - 1) can be used to balance the block )
get a byte, put it in the block
z = num 0s in block
o = num 1s in block
z = b - z // num 0s needed to balance block
o = b - o // num 1s needed to balance block
assert( (z<8) || (o<8) );
if( o < z ) {
assert( o > 0 && o < 8 )
put the value (0xFF >> o) in block
z = z - (8 - o)
fill rest of byte with z/8 0xFF values
} else if( z < o ) {
assert( z > 0 && z < 8 )
put the value (0xFF >> (8-z)) in block
o = o - (8 - z)
fill rest of byte with o/8 0x00 values
} else {
assert( z == 4 && o == 4 )
put the value 0xF0 in block
}
> This expansion of the data will, I fear, like the autokey nature
> (making for poor error-recovery properties) of Dynamic Substitution,
> condemn Dynamic Transposition in the specific form described here to
> marginality.
Only if you try to balance very small blocks using the method which you
invented, rather than using normal sized blocks (128 or 256 or 512
bits).
If one compresses first, there's almost no data expansion, since with
any good compression scheme, the output is almost always nearly
bit-balanced.
> The market does not want to hear of encryption methods
> that are awkwards - that can't be used, for example, to encrypt a
> sector of a disk and fit the encrypted result in a sector of a disk.
Well, considering that with Ritter's scheme for bit balancing, which I
described above, there is *always* one byte of message expansion per
block, we almost certainly would not want to use this to encrypt disk
sectors -- simply because, for disk sector encryption, we want little or
no expansion.
However, for encrypting a stream, or a file [at user level], this is not
as much of a problem. One byte of expansion for every 32 bytes of
message is acceptable.
> Combining substitution and transposition - and using a Feistel-like
> structure to make the transposition key for one half of a block depend
> on the contents of the other half (thus obtaining the variability Mr.
> Ritter rightly notes as essential to avoid multiple anagramming) - is
> capable of producing a much more well-behaved and "conventional"
> cipher.
The "transposition key," which you speak of as if it were the key to a
normal block cipher, is actually the key of a PRNG, whose output is fed
into a function which shuffles bits. The PRNG is not rekeyed between
blocks.
> This is not to say, however, that the concepts presented here are not
> useful. Terry Ritter has shown how one _could_, even at the cost of
> inconveniences people aren't usually willing to bear, make a secure
> cipher based on transposition alone.
The inconvenience is that of the expansion due to bit balancing blocks.
With his scheme for doing this, there is very little expansion, and thus
little inconvenience. Expansion is minimized if one compresses before
encrypting, which is done anway with most good schemes.
> This is of theoretical significance, and that, all by itself, is
> genuinely valuable.
>
> (It might also be noted that the requirement that each transposition
> step must uniformly be capable of producing all N! permutations of
> bits is likely to make the transposition steps computationally
> inefficient, so I think that this is another unfashionable aspect of
> the specific proposal given. Although in this case, unfashionable does
> not mean unsound: that is a desirable ideal.)
for( i = N-1; i > 0; --i ) {
swap( bit[i], bit[ PRNG_ranmod(i+1) ] )
PRNG_ranmod *can* be made unbiased and fairly efficient, and if it is,
then we will have an unbiased selection of all N! transpositions.
> The fact that bit balancing is not going to produce, by any reasonable
> algorithm, all N!/(N/2)!^2 possible bit-balanced blocks as input to
> the transposition, my earlier objection to this scheme, also impinges
> on the value of this...
I thought that the number of bit balanced, N bit blocks was (N/2)!(N/2)!
Of course, I haven't done combinatorics in a while, so I might be wrong.
Anyway, since every bit-balanced block is a permutation of any other
bit-balanced block, it doesn't matter. If all encryption permutations
are equally likely (which they are), your point is invalidated.
Your statement is akin to saying that since all 2^N plaintexts are not
equally likely, OTP is insecure. My response is analogous to saying
that if all pads used in OTP are equally likely, then it doesn't matter
if the plaintexts are biased.
If a Truly Random string of bits is used instead of a PRNG, (and this
string is used once), then, informationwise, this system is precisely as
secure as OTP, AFAIKS.
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 19 Jan 2001 07:23:29 GMT
John A. Malley wrote:
>
> Terry Ritter wrote:
> [snip]
> >
> > One of the needed components which has not been described
> > is the bit-balancing process.
> >
> > Bit-Balanced Blocks
> >
> > Some of the analytic and strength advantages of Dynamic
> > Transposition depend upon having the same number of 1's
> > and 0's in each block, which is called "bit-balance."
> > Exact bit-balance can be achieved by accumulating data to
> > a block byte-by-byte, only as long as the block can be
> > balanced by adding appropriate bits at the end. Then the
> > block is ciphered, and another block filled.
> >
> > We will always add at least one byte of "balance data,"
> > at the end of a block, and only the first balance byte,
> > immediately after the data, will contain both 1's and 0's.
> > We can thus transparently remove the balance data by
> > stepping from the end of the block, past the first byte
> > containing both 1's and 0's.
>
> I had a few immediate hunches about cryptanalysis of dynamic
> transposition but realized they may spring from misunderstanding of
> the algorithm.
>
> May I paraphrase the description of block balancing to make sure I
> understand the mechanism as envisioned? And please, correct me if I
> got this wrong.
>
> Given plaintext P,
>
> 1) divvy P into bytes as P[1], P[2], P[3] ... P[n],
>
> 2) build up (one at a time) blocks of size k bytes, B[1], B[2], B[3]
> ... B[m] where m < n, and sequential plaintext bytes are assigned to
> a given block B[i] where B[i] is the concatenation of a few plaintext
> bytes, followed by a special byte that has 0s and 1s in it, followed
> by bytes of all zeros or all ones - like
>
> P[1] | P[2] | ... | P[L] | a block of 1s and 0s | 00000000 |
> 11111111 | ... 00000000 = B[i]
>
> or
>
> P[1] | P[2] | ... | P[L] | a block of 1s and 0s | "0" | "255" | ...
> "0" = B[i]
>
> Is this an accurate description of the proposed bit balancing?
Almost. It's more like
if( P[1..L] has more 0s than 1s ) {
P[1] | P[2] | ... | P[L] | XXXXXXX | 00000000 | 00000000 = B[i]
Where XXXXXXXX is some number of 1s and 0s.
} else {
P[1] | P[2] | ... | P[L] | XXXXXXX | 11111111 | 11111111 = B[i]
Where XXXXXXXX is some number of 0s and 1s.
}
Only when the plaintext reaches EOF does it look at all like your
example.
Here's some C code, to [hopefully] make things clear:
unsigned char balanced[16]; // 128 bits
unsigned int bp = 0; // pointer to balanced data.
unsigned int z = 0, o = 0; // zeros, ones.
extern unsigned h(unsigned); // hamming weight
do {
unsigned char rnext = peekc();
unsigned int zn = z+h(rnext);
unsigned int on = o+8-h(rnext);
if( abs(zn-on) >= 64 ) break;
balanced[bp++] = getc();
z = zn; o = on;
} while( bp < 15 );
z = 128 - z; o = 128 - o;
// change from how many 0s and 1s are there, to how many are needed?
if( o < z ) {
balanced[bp++] = 0xFF << (8-o);
while( bp < 16 )
balanced[bp++] = 0x00;
} else {
balanced[bp++] = 0xFF >> z;
while( bp < 16 )
balanced[bp++] = 0xFF;
}
Thus, blocks are either
raw data, balance byte, 0 or more 0xFF bytes
or
raw data, balance byte, 0 or more 0x00 bytes.
To reverse the transform, we do the following:
if the last byte is 0x00, then we remove all 0x00 bytes from the end,
and the first non-0x00 byte.
if the last byte is 0xFF, then we remove all 0xFF bytes from the end,
and the first non-0xFF byte.
otherwise, we simply remove the last byte.
The data near the EOF is handled slightly differently, of course, but
I'm not going to write code for it now (if ever).
> I'm curious about fixed bit patterns or expected bit patterns (if any)
> that end up in the appended plaintext, for they may serve as the chink
> in the armor for cryptanalysis.
Do expected bit patterns/fixed bit patterns in plaintext provide a chink
in the armor of OTP?
--
Most scientific innovations do not begin with "Eureka!" They begin with
"That's odd. I wonder why that happened?"
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: block algorithm on variable length without padding?
Date: Fri, 19 Jan 2001 07:22:42 GMT
"Adrian S. Thompson" wrote:
> By placing an EOF (End Of File) at the beginning of the padding after encrypting
> will trick the file system into thinking the file was as long as it was before
> the padding as added.
its completely senseless.
encrypted file is BINARY file, and contains all 256 character including EOF
if file is 77K long there should be about 300 EOF characters in this file.
besides padding can not be removed - if you remove it you can not decrypt last block !
only solution is to use some chaining mode (as mentioned in other posts)
and even with this its possible to retain file length only if it file length >=
blocksize.
== <EOF> ==
Disastry http://i.am/disastry/
http://disastry.dhs.org/pgp <-- PGP plugins for Netscape and MDaemon
remove .NOSPAM.NET for email reply
------------------------------
From: Arturo <[EMAIL PROTECTED]=NOSPAM>
Crossposted-To: talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Fri, 19 Jan 2001 08:38:14 +0100
On Thu, 18 Jan 2001 17:35:41 GMT, [EMAIL PROTECTED] (Jim Haynes) wrote:
>In article <3Hl96.51$[EMAIL PROTECTED]>,
>Mysterion <[EMAIL PROTECTED]> wrote:
>>Sounds like Microsoft is determined to shoot themselves in the foot.
>>
>When you're a monopoly you can shoot yourself in the foot as often as
>you like.
And make Torvald happier and happier. Microsoft might believe he�s the
numero uno, but I�ve been in places (research centers, newspaper offices) where
Gates� products were the exception rather than the norm. They think they can do
whatever they want? Fine. Standard Oil and AT&T also thought so in their time.
------------------------------
Date: Fri, 19 Jan 2001 09:38:00 +0100
From: Pascal Junod <[EMAIL PROTECTED]>
Subject: Hierocrypt-L1
Has anyone a working implementation in C of Toshiba's
Hierocrypt-L1 ?
A+
Pascal
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
* Pascal Junod, [EMAIL PROTECTED] *
* Laboratoire de S�curit� et de Cryptographie (LASEC) *
* INF 240, EPFL, CH-1015 Lausanne, Switzerland ++41 (0)21 693 76 17 *
* Place de la Gare 12, CH-1020 Renens ++41 (0)79 617 28 57 *
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Kooks (was: NSA and Linux Security)
Date: Fri, 19 Jan 2001 08:41:17 GMT
On Thu, 18 Jan 2001 22:24:02 GMT, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote, in part:
>Greggy wrote:
>> > > > legally declared the citizens of the US enemies of the US
>> "During time of war or during any other period of national emergency
>> declared by the President, the President may ... regulate ...
>> any transactions in foreign exchange, ... hoarding, melting, or
>> earmarkings of gold or silver..., by any person within the United
>> States or anyplace subject to the jurisdiction thereof".
>That is not a declaration of US citizens as "enemies". You're
>reading too much into the title of the Act -- does the Gun Owners'
>Protection Act of 1968 really protect gun owners? The titles are
>for mnemonic and reference purposes only.
>It is obvious that the purpose behind the amendment was to close
>a loophole whereby US citizens could abet the enemy by acting as
>their agent in such transactions.
Oh? That was the concern during the period from 1933 to 1975?
Of course, the United States is a large and powerful country. Thus, it
bears a big responsibility for the world.
So it makes sense that sometimes U.S. citizens face certain
limitations that people in other countries do not, such as
- a limit on owning gold, during a time when it was felt the world
needed more currency in circulation to keep the economy going,
- conscription for the war in Vietnam that few other nations
(Australia was one of that few) felt was essential to the defence of
freedom,
- restrictions on crypto export, since the U.S. is a world leader in
computer technology.
Instead of criticizing the U.S. for this, I can understand why some
people might feel other countries should look at themselves to see if
they are freeloading.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Dynamic Transposition Revisited (long)
Date: Fri, 19 Jan 2001 08:56:50 GMT
On Fri, 19 Jan 2001 06:26:38 GMT, Benjamin Goldberg
<[EMAIL PROTECTED]> wrote, in part:
>only one of the balancing bytes will contain both ones and zeros, and
>that will be the first balancing byte. All of the rest of the balancing
>bytes, from there to the end of the file, will contain all ones, or all
>zeros.
Yes, you're right. I disliked simple padding enough not to think
through whether or not it might be workable.
quoting me:
>> Of course, a *simple* way of dealing with this problem would be to
>> code 6 bits of binary input to an 8-bit byte in a 4 of 8 code, using
>> 64 of the 70 possible values. This would be a brute-force approach,
>> but it would mean that one would not have a data-dependent concern
>> with the block lengths. They could be uniform, or chosen randomly.
>Huh? I don't get what you're saying.
I considered just balancing each byte as I went along, simply because
it was more straightforwards.
>We have a nice big 128 bit block. We shuffle all the bits in it. We
>are not shuffling the bytes in it. If bits were balanced before
>shuffling the bits, they will certainly be balanced after we shuffle the
>bits.
That wasn't the problem I was thinking of. I was thinking of the data
expansion needed to balance the bits - and an additional data
expansion caused by the transposition messing up any shortcuts we took
to do the balancing, so that I couldn't take the balanced output and
convert it to the same number of unbalanced bits as I got as input.
>> The fact that bit balancing is not going to produce, by any reasonable
>> algorithm, all N!/(N/2)!^2 possible bit-balanced blocks as input to
>> the transposition, my earlier objection to this scheme, also impinges
>> on the value of this...
>I thought that the number of bit balanced, N bit blocks was (N/2)!(N/2)!
>Of course, I haven't done combinatorics in a while, so I might be wrong.
Here, I know I'm right.
Arrange the characters of the string
abcd1234
in all possible ways, and there are 8! possibilities.
Now, replace each of the characters abcd by zeroes. You have
eliminated the 4! different ways of arranging those letters, so the
number of different possibilities is now 8!/4!.
Replace each of 1234 by 1, and you have divided by 4! yet again.
Thus, 8*7*6*5/4*3*2*1 = 2*7*5 = 70, the number of characters in a 4 of
8 code. (Which is why I can change 6 bits to 8 bits, get guaranteed
bit balance, and not have to do anything funny, at the cost of extra
redundancy.)
>If a Truly Random string of bits is used instead of a PRNG, (and this
>string is used once), then, informationwise, this system is precisely as
>secure as OTP, AFAIKS.
This is true, if the input is fully balanced, not just approximately,
because the method calls for all N! permutations to be equally likely
in this case. That's why I agree it is important from the theoretical
standpoint, it shows that transposition can be used alone to create a
cipher of serious strength.
I still ask, would anyone want to do it, because it appears to me this
has a bandwidth cost that people will see no need to incur.
I assumed that bit-balancing is done over smaller extents than
transposition, because in the practical non-OTP case, the largest
possible transposition block improves security.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.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
******************************
