Re: Question about bit strength

On Thu, 14 Sep 2006 09:38:03 +1000, "Antony Clements"
<antony.clements@xxxxxxxxxxxxxxx> wrote:

Some comments on your algorithms:

Method 1 algorithm

Begin
Create Keys
Ensure each key is unique
Crypto: This is a weakness. When the arracker is brute-forcing keys
she does not have to try combinations with duplicate keys. This
reduces the amount of work she has to do. I know why you do it (A xor
A = 0) but it is better to pick a different way to generate what is
effectively a single key (see below) and allow the whole keyspace to
be available rather than just part of it.

Get FileContents
DivisionResult = len(FileContents \ len(Key)
Typo: mismatched brackets. Also below but not noted.

If DivisionResult is not an integer then
Do until DivisionResult is an integer
FileContents = FileContents & Chr(0)
Code: If you want to remove the padding correctly you need to record
how much padding you are adding.

DivisionResult = len(FileContents \ len(Key)
Loop
Code: Hideous code. Doesn't VB have the mod operator?

End if
Index = 0
Get DataBlock
Do until end of file
Index = 0
Do until Index = (amount of keys - 1)
EncryptedData = DataBlock XOR Key(Index)
Crypto: This calculates cyphertext = plaintext xor key1 xor key2 xor
key3 ... This can be written as c = p xor (k1 xor k2 xor k3 ...)
which reduces to p = c xor K. Better to use a single K and hence
avoid the keyspace reduction problem I mentioned above.

Increment Index
NewData = NewData & EncryptedData
Code: Shouldn't this be outside the loop?

Loop
Get next DataBlock
Loop
Remove file padding
Create NewFile
Write NewData in NewFile
End

This is basically a stream cypher with some extraneous blocking added.
You have a single key, disguised by breaking it up into pieces which
are then XORed together. The key is repeated if the plaintext is
longer than the key which is a major weakness. The added blocking
does nothing for the cypher, if you removed the blocking then you
could drop the padding.

A standard stream cypher operates by setting up a PRNG and seeding it
with a key and nonce
(http://en.wikipedia.org/wiki/Cryptographic_nonce). The PRNG
generates a stream of bytes which are XORed with the plaintext to
produce the cyphertext:

function Encrypt(plaintext, nonce, key) returns cyphertext
Initialise_PRNG(nonce, key)
cyphertext = empty byte array
foreach (byte p in plaintext)
append (p xor Next_Byte_From_PRNG()) to cyphertext
end foreach
return cyphertext
end function

function Decrypt(cyphertext, nonce, key) returns plaintext
Initialise_PRNG(nonce, key)
plaintext = empty byte array
foreach (byte c in cyphertext)
append (c xor Next_Byte_From_PRNG()) to plaintext
end foreach
return plaintext
end function

The PRNG is used to stretch the key to cover the entire plaintext
without repetition. The nonce ensures that the PRNG output is unique
within a given key. A simple example of a stream cypher is RC4
(http://en.wikipedia.org/wiki/RC4) which is no longer properly secure
but is an easy stream cypher to understand.


Method 2 algorithm
This is still basically a stream cypher. You generate a longer key by
rearranging the shorter key and concatenating. This does not add any
extra security since the attacker can easily perform exactly the same
rearrangements. The extended key is repeated if the plaintext is
longer which is a major weakness. A One Time Pad is secure in part
because it is only ever used once (hence the name). A One Time Pad
used twice is no longer secure and what you have here is a effectively
a "Many Times Pad" which is definitely not secure.

Repeating keys are dangerous because they allow the attacker to remove
all key information. Each cyphertext byte (c) is a plaintext byte
(p) XORed with a key byte (k). If the attacker knows that two
different cyphertext bytes have been encyphered with the same key byte
then she can XOR the two cyphertext bytes together:

c_m = p_m xor k_m
c_n = p_n xor k_m - the same key byte is used

c_n xor c_m = (p_m xor k_m) xor (p_n xor k_m)

since k_m xor k_m = 0, this reduces to

c_n xor c_m = p_n xor p_m

The attacker has now completely removed the key. All she has to do is
to XOR the cyphertext with itself at different offsets and some of the
resulting byte strings will have all the key information removed.
Repeating at 2 x offset, 3 x offset etc. will give her yet more
information about the original plaintext, leading to a decryption.
With even a partial plaintext recovery, some or all of the key can be
recovered and the cypher is broken.

To avoid the problem of key repetition the One Time Pad has a key as
long as the plaintext while a stream cypher uses a PRNG to stetch the
key to the required length. For your purposes a stream cypher will be
easier.

rossum

.

Relevant Pages

  • Re: Steganography - Encryption challenge
    ... it's easy enough to make up one which will make the plaintext fit the ... encrypted messages available to the public increases, ... access to the application which produced the cyphertext allows you to ... the algorithm and you have some idea about the implementation. ...
    (borland.public.delphi.non-technical)
  • Re: PRNG using two functions
    ... length and the output is a fixed permutation of ... Maybe the sentence "The same plaintext produces the same cyphertext." ... Obtaining the plaintext? ...
    (sci.crypt)
  • Re: Strongest encryption algorithm
    ... no bit in the plaintext should encode to the same bit in the ... Interesting extrapolation, but it only applies on a bit sized alphabet, ... resulting cyphertext had zero L's in it. ... Enigma had been broken before then, before the war, in fact, by the Polish. ...
    (sci.crypt)
  • Re: Strongest encryption algorithm
    ... no bit in the plaintext should encode to the same bit in the ... The same applies when you work on the character, or even file level, ... Interesting extrapolation, but it only applies on a bit sized alphabet, ... resulting cyphertext had zero L's in it. ...
    (sci.crypt)
  • Re: Can this be done with a symmetric cipher?
    ... a stream cipher can be used for this.. ... called the keystream, to produce the cyphertext. ... XOR is both commutative and associative so we can rearrange this ...
    (sci.crypt)
Quantcast