symmetric encryption

[mindevolution]

ok i've looked at a lot of the symmetric encryption algorithms, however, they usually only have up to 256bit keys eg AES.

so i have this code that allows any length file to be used for a text key (cryptkey). does this make the following algorithm stronger?


Private Sub Crypt(Path As String, CryptKey As String, CryptNumber As Double)
' 1. loads file to be encrypted in Path, into a bite array
' 2. loads in any length file contained in CryptKey into a bite array and xors it
'against the stream of bits of file to be encrypted

If Len(Dir$(Path)) Then
Dim ba() As Byte, nba() As Byte, kba() As Byte, i&, n&, ff&
n = FileLen(Path)
ReDim ba(n - 1): ReDim nba(n - 1) ' Resize byte arrays to hold all bytes in file
ff = FreeFile
Open Path For Binary Access Read As #ff
Get #ff, , ba() ' read file into byte array
Close #ff
Kill Path ' kill existing file now have file in ba()

n = Len(CryptKey) ' get length of CryptKey
kba = StrConv(CryptKey, vbFromUnicode) ' convert CryptKey into byte array
Rnd -1 ' calling rnd with a negative number before randomize allows rnd sequence to be reproduced
Randomize CryptNumber
For i = 0 To UBound(ba)
nba(i) = ba(i) Xor kba(i Mod n) Xor Int(Rnd * 256) 'Xor each byte with a random number as well as CryptKey
Next i

ff = FreeFile
Open Path For Binary Access Write As #ff
Put #ff, , nba() ' Write encypted bytes back to file
Close #ff
End If
End Sub

[mindevolution]

with such small key sizes for the authorised algorithms, do they want people to be insecure? 256 bits is tiny!:eek:

with the algorithm I posted and using a very large text file as the key, it has to be a million times more secure than the "authorised" symmetric encryption algorithms. :lol:

or am i missing something?

[koutote]

:) I am afraid NO!

Your encryption is quite simple and I would say quite dangerous
to be decrypted easily. Do not underestimate the current well known
encryption algorithms, such as AES etc, they might have only 128 or
256 bits long cipher keys however their strenght is not coming from
the length only. Have many other properties such as many iterations,
shifts, replacements in Galois mathematics and others which make them stronger and immune in attacks and even in brute force cases.

And a software programming note, by killing a file this does not mean
that is being deleted from your hard disk drive!

[mindevolution]

thanks for the reply, however, with a 128/256 bit key, i think such encryption is not strong and I am wary of it. for example the Rijndael algorithm can be changed to accept a key of any length key:

http://www.iaik.tugraz.at/research/krypto/AES/old/~rijmen/rijndael/

"Both block length and key length can be extended very easily to multiples of 32 bits"

however, the majority of the implementations are restricted to 128/256 bits which means they have crippled the strength of their encryption on purpose. I do not trust such crippled protection :mad: . it seems like most people think they are securely protected, when they are not, and could be much much better protected.

xor encryption is strong encryption depending on key size, and many of them include it if not all, if you look at their algorithms eg http://en.wikipedia.org/wiki/International_Data_Encryption_Algorithm

sure they shift a block here and shift a column there, however, at the end of the day it is the key size that matters the most in terms in terms of offering extra protection. squeezing more "protection" from 256 bytes seems like a waste of time to me.

i have unlimited key size in my app and regularly use 30 page documents as keys for my encryption and encrypt entire sections of my harddrive quite quickly. :D if you think about it you only have to load in the large key file into memory once and apply it to all the files on your harddrive, which means it is possible to have absoultely huge key files and fast encryption like my app.

it may not be overly complicated, but xor with large keys is highly effective, and i would trust it over a tiny little 256 byte key.

can someone explain why they insist on such small keys?

i am working on the kill problem at the moment :blush:

[mindevolution]

i realised the rnd function is only 32 bits and can be decompiled from the application, and so it doesn't offer any proper protection. so it is now out of the algorithm. :)

next thing I noticed was that when the length of any file is less than the length of the key, the algorithm doesn't apply the whole key to the file. So in effect there is less protection for small files. I think I will need to fix this part of the algorithm.

any other weaknesses?

[koutote]

Ok, this is quite interesting topic....:)

My comments below:

1. Your link in wikipedia refers to IDEA which applies XOR but this
is the case for Rijndael too ;)

2. Yes, your encryption method is faster than AES but also more
simple....As you already state, what happens if your original file
that you want to encrypt is only 90 bytes long (a simple text?)

3. I think that an expert on attacks with tools like brute force and a good dictionary on your language you encypt (or even with library of words, sentences etc ) will decrypt your files easily. Try any byte, then next one
next etc....until he finds the correct byte that make a sence word....
You should add I think some convolution in time (as in IDEA i think) at least
to eliminate this....

4. The Rijndael has 128 bits key lenght, but at the same time this key is expanded for each iteration, for 10 iterations you have 1280 bits long
However authors claim that keys between iterations are independent but
this is another question.....

[mindevolution]

Ok, this is quite interesting topic....:)

My comments below:

1. Your link in wikipedia refers to IDEA which applies XOR but this
is the case for Rijndael too ;)

true :)

2. Yes, your encryption method is faster than AES but also more
simple....As you already state, what happens if your original file
that you want to encrypt is only 90 bytes long (a simple text?)

its faster and the key size is unlimited. i have not solved the small file problem yet, i will think about it overnight.

i have fixed the kill problem, i just overwrite the data and then rename the file, rather than write to a new file and killing the old one. although is overwriting the data once enough to destroy the image on the harddisk? :confused:

3. I think that an expert on attacks with tools like brute force and a good dictionary on your language you encypt (or even with library of words, sentences etc ) will decrypt your files easily. Try any byte, then next one
next etc....until he finds the correct byte that make a sence word....
You should add I think some convolution in time (as in IDEA i think) at least
to eliminate this....


i just tried to brute force my own files like you said, however, my computer stopped while trying all the permutations from a string 4 chars long, and that was while restricting it to regular alpha numerics. :eek: I think brute force with a large key file is impossible with today's computers. to brute force a file with a 30 page document as a key is not even within the realms of imagination with current computing power.

in the future there will be a way to brute force even large key files, however, people will just keep expanding the size of the key files that they use. which is why they slowly increase the size of the keys for the public to use with the symmetric encryption, while keeping it short enough so they can get access if needed.

so xor encryption is timeless as a concept as long as the key size increases with the strength of computing. :)

you do raise a good point though, distorting time brings time travel into the discussion. and it is possible into the future as we have experimental proof, but no proof that time travel into the past is feasible although some quantum mechanic models suggest it is, although they are theoretical arguments for now. so this makes xor encryption safe into the future unless there is proof that backwards time travel is possible ;)


4. The Rijndael has 128 bits key lenght, but at the same time this key is expanded for each iteration, for 10 iterations you have 1280 bits long
However authors claim that keys between iterations are independent but
this is another question.....

at the end of the day it doesn't matter what they do in the algorithm, with 128 bit keys there is 2^128 permutations and with 256 bit keys 2^256 permutations, so more complicated algorithms with small keys don't impress me, they waste time without making brute force more difficult. A 256 bit key is child's play if you compare it to the number of permuations from a 1MB key file or longer :D. also having an unknown and variable key length adds much more strength to the encryption.

[mindevolution]

ok for some maths

if the key is 1 byte long there are
256 cominations

if the key was 10 bytes long
256^10 cominations
= 1,208,925,819,614,629,174,706,176 :eek: *yikes*

my 30 page document as a key, is 47KB
that is
256^47000
= broke windows scientfic calculator :D ;)

anyone who says xor is not safe with a long key is stupid ;)

[sunburnt]

Assuming
1) Your key is the same length as the data to encrypt
2) Your key is completely random
3) Your key is never reused


However, if your key is shorter than the data to encrypt, or if you reuse the key over several documents, then it is possible to identify patterns in the encrypted data that make it easier to break.

If your key is not completely random (ie, it's A-Z,0-9, etc), then the values for each byte falls in a much smaller range, which makes it easier to attempt to guess a key as well as to identify bits that will not have been changed.

[mindevolution]

hi Sunburnt?
is that Shannon's theorem?

[mindevolution]

mybad, with all of the numbers I calculated, I should have said permutations not combinations :)

[mindevolution]

also a one extreme if the key was all bytes = 0, then there would be no encryption at all. so making sure the key has all bytes set to be>1 is essential.

[koutote]

I post something on Friday but was lost mysterioysly.....

OK, mindevolution, I think, I would I agree the longer the key
the better the encryption, but depends on the application and
the way you apply this key.

Take into consideration the following simple senario:

If you apply your long key (from the 40Mbytes files) in all original
files you want to encrypt (A, B, C etc) then if somebody, somehow
will know the pair A, F(A) ( F(A) is the encrypted file) then its
a child's play (as you said...:) ) to inverse the XOR function, find your
LONG key, and decrypt ALL the files....B, C etc....
This is not the case however with AES algorithms where even if you know
the pair A, F(A) you still have to rely on brute force or other deep mathematical tools basend on assumptions and probabilities....

In case you want to encrypt EACH file whith different key (of length 40Mbytes) then for each you must generate a new 40 Mbytes, which is not
very efficient way....to say not appplicable in many applications where neither you have enough space nor enough time to do it!!!

Finally just a question, how much time (in secs, mins, hours, years,..whatever..) does a typical PC need to generate all these 2^128 bits combinations? (Actually in order to crack the key you need 2^127 but anyway....). Can you do a rough calculation?

[koutote]

I post something on Friday but was lost mysterioysly.....

OK, mindevolution, I think, I would I agree the longer the key
the better the encryption, but depends on the application and
the way you apply this key.

Take into consideration the following simple senario:

If you apply your long key (from the 40Mbytes files) in all original
files you want to encrypt (A, B, C etc) then if somebody, somehow
will know the pair A, F(A) ( F(A) is the encrypted file) then its
a child's play (as you said...:) ) to inverse the XOR function, find your
LONG key, and decrypt ALL the files....B, C etc....
This is not the case however with AES algorithms where even if you know
the pair A, F(A) you still have to rely on brute force or other deep mathematical tools basend on assumptions and probabilities....

In case you want to encrypt EACH file whith different key (of length 40Mbytes) then for each you must generate a new 40 Mbytes, which is not
very efficient way....to say not appplicable in many applications where neither you have enough space nor enough time to do it!!!

Finally just a question, how much time (in secs, mins, hours, years,..whatever..) does a typical PC need to generate all these 2^128 bits combinations? (Actually in order to crack the key you need 2^127 but anyway....). Can you do a rough calculation?

[mindevolution]

I post something on Friday but was lost mysterioysly.....

OK, mindevolution, I think, I would I agree the longer the key
the better the encryption, but depends on the application and
the way you apply this key.



Hi koutote


Take into consideration the following simple senario:

If you apply your long key (from the 40Mbytes files) in all original
files you want to encrypt (A, B, C etc) then if somebody, somehow
will know the pair A, F(A) ( F(A) is the encrypted file) then its
a child's play (as you said...:) ) to inverse the XOR function, find your
LONG key, and decrypt ALL the files....B, C etc....



sure, however, how does the 3rd party get the original file, if you only send it encrypted? why would you ever send an encrypted file and its original version to anyone, in the same way you wouldn't send the key and the encryption to anyone? :confused:

if they get the original then they must have access to your computer. if you store your confidential files in encrypted form on your pc, it is then just the key that is the weakness and the key can be stored anywhere, physically or in cyberspace.

now the conversation is interesting. :)



Finally just a question, how much time (in secs, mins, hours, years,..whatever..) does a typical PC need to generate all these 2^128 bits combinations? (Actually in order to crack the key you need 2^127 but anyway....). Can you do a rough calculation?

ok well each permutation = 1 binary number
it takes 1 sec for 100 million numbers on my pc

that means for a 128 bit key
2^128 or 256^16 = 3.4 * 10^38 different numbers

that would take 10^30 seconds which is a long time!

but that is for the longest time, the shortest time is 0 seconds and both are not very likely to happen. if the key is random and is a low number, or the user puts in a low number as they can only remember 4 to 6 digits, then it is much quicker to find the key. also with many computers working on the problem and with faster pcs, there is a chance to find the key much faster.

with a high tech lab, with lots of today's computing power it would probably take months or even quite a few years to find a well constructed 128 bit key on average, 256 bits much longer.

however, with my keys which can be megabytes or bigger, it makes 128 or 256 bit keys look funny :)

[mindevolution]

ok, another thing i noticed, if the file byte is 0 no need to xor it

and if the file byte is the same as the key byte no Xor either.

[mindevolution]

i have read about frequency attacks, what are they?

[mindevolution]

another thing i noticed was that there is a lot of people saying that "one time pads" are unbreakable.

however if you only have a short message:

"one time pads"

there are 255^13 permutations. so even 1 time pads with random keys are breakable.

[mindevolution]

also I found this from Applied Cryptography

Bruce Schneier


It's an embarrassment to put this algorithm in a book like this because it's nothing more than a Vigenere cipher. It is included because it is so prevalent in commercial software packages, at least those in the MS-DOS and Macintosh worlds[1]. Unfortunately, if a software security program proclaims that it has a "proprietary encryption algorithm" -- one that is significantly faster than DES -- the odds are that it is some variant of this:
... snip basic XOR code and some comments about it ....

There is no real security here. This kind of encryption is trivial to break, even without computers [2, 3]. It will only take a few minutes with a computer.

Assume the plaintext is English. Furthermore, assume the key length is an arbitrary small number of bytes. Here's how to break it:

1. Discover the length of the key by a procedure known as counting coincidences[4]. Trying each byte displacement of the ciphertext against iself, count those bytes that are equal. If the two ciphertext portions have used the same key, something over 6% of the bytes will be equal. If they have used a different key, then less than 0.4% will be equal (assuming a random key encrypting normal ASCII text; other plaintext will have different numbers). The smallest displacement that indicates an equal key is the length of the repeated key.

2. Shift the ciphertext by that length and XOR with itself. This removes the key and leaves you with the plaintext XORed with itself, shifted by the key length. Since English has about one bit of real information per byte, there is plenty of redundancy for choosing a unique decryption.


that is not a true statement, let me show you:



Private Sub Command1_Click()
Dim s$, key() As Byte, i&, ba() As Byte, baNew() As Byte
s = "Shift the ciphertext by that length and XOR with itself. This removes the key and leaves you with the plaintext XORed with itself, shifted by the key length. Since English has about one bit of real information per byte, there is plenty of redundancy for choosing a unique decryption."
key = StrConv("key", vbFromUnicode)

ba = StrConv(s, vbFromUnicode)
ReDim baNew(0 To UBound(ba))

For i = 0 To UBound(ba)
baNew(i) = ba(i) Xor key(i Mod 2)
Next i

For i = 0 To UBound(baNew)
s = s & Chr(baNew(i) Xor key(i Mod 2))
Next i

Debug.Print s

End Sub


now to decrypt without the key, knowing only that the key it is 3 characters...

well we know the first character is "S" which is a byte value of 83 when xored with the "k" of key which is a byte value of 107 = 56

in order to decrypt from 56 to "S", it needs to be xored with 107 again, but bruce wants us to xor it with the 4th character of the encrypted string which is 3. I believe that is gross misinformation about Xor encryption. He is writing something blatantly wrong and misleading on purpose ;) they do not want the public to know how strong Xor is. :)

[mindevolution]

oh and another thing, with Xor, getting the pattern just tell you the length of the key, it doesn't help you find the key, that still needs brute force :)

[mindevolution]

so it is no harder to break a random key code than a non random key code:

this is how to work out the length of the key for the xor algorithm, pass in millions of bytes of the same character say "a" for example and soon a pattern will emerge, whether it was randomly generated makes no difference when using large sized keys.

the pattern may occur every 3 characters ie a 3 byte key = 256^3 permutations of the key

or the pattern may occur every 1000 characters ie 256^1000 permutations.

so finding a pattern with Xor doesn't help break the key, it just tells you how big the key is, and the length of key is already known for all the major key size limited algorithms.

so frequency analysis cannot find the key, just tell you how big it is :D

[mindevolution]

it is possible to make xor harder to decode than a one time pad ;) :)

and without any randomness to the keys :D

[mindevolution]

also reusing a key doesn't make it weaker, because finding a pattern doesn't help find the key.

[mindevolution]

so, sunburnt:

Assuming
1) Your key is the same length as the data to encrypt
2) Your key is completely random
3) Your key is never reused


i don't agree, the security only has to do with the length of the key and not with any of 1,2, or 3. :)

[mindevolution]

it is possible to make xor harder to decode than a one time pad ;) :)

and without any randomness to the keys :D

ah yes, the key may not be random, but then you would have to apply some degree of randomness to the process wouldn't you? ;)

[mindevolution]

ah yes, the key may not be random, but then you would have to apply some degree of randomness to the process wouldn't you? ;)

yes that's true ;) :D

[mindevolution]

yes that's true ;) :D

you know you really must think of someway to deal with a plaintext attack don't you think?

[mindevolution]

you know you really must think of someway to deal with a plaintext attack don't you think?

ok, i think about it and get back to you :)

[mindevolution]

ah, so that was what all the fuss is about, plain text attacks. they have to make the algorithm complicated and slow to protect against the risk of sending a document and an original together at the same time?:rolleyes: :D

they are funny people who spend all their time on a silly non probable scenario. i think that most people will never in their life send an original and an encrypted file to another person. ;) :D

so all the algorithms try to protect from a non probable event, plain text attacks, and don't offer enough protection from probable brute force attacks, which is a real probablility due to increasing computing power :mad: ;)

when DES fist came out in 1977 (precusor to AES), there was a machine proposed by Diffie and Hellman that could find a DES key quickly in the same year for 20million US :mad: that means that brute force is the biggest problem, not plain text attacks ;)

am i naive to think that AES keys cannot be found by governments with large budgets today, nooooo!;) :mad:

[mindevolution]

so if you want protection from almost non probable plain text attacks, but limited protection from brute force attacks and let in the government, use a regular algorithm like AES. :cry:

if you don't care about plain text attacks as they are almost never going to happen, and you could always reencrypt anyway, and you want fast efficient protection from brute force attacks that even keeps the government away, Xor + large key size is the operator for the job. :)

wihtout plain text attacks, there are no problems with non random keys, keys not being the same length as the text, and you can reuse the key as much as you want. :D :thumb:

[mindevolution]

so if you want protection from almost non probable plain text attacks, but limited protection from brute force attacks and let in the government, use a regular algorithm like AES. :cry:

if you don't care about plain text attacks as they are almost never going to happen, and you could always reencrypt anyway, and you want fast efficient protection from brute force attacks that even keeps the government away, Xor + large key size is the operator for the job. :)

wihtout plain text attacks, there are no problems with non random keys, keys not being the same length as the text, and you can reuse the key as much as you want. :D :thumb:

you know it isn't difficult to make xor safe from plain text attacks too ;), then that could be an issue of national security though :D bishop takes queen

[dunno]

Do you know the performance of symmetric encryption ?
In particular, how many bits per second using the XOR method ?
Or, I guess I should ask how many cycles does a XOR gate takes ?
Thanks in advance.

[cleverconcepts]

easily stated:

Xor performance > any other published encryption algorithm.

[dunno]

The One Time Pad is very efficient but requires 1 random bit for every plaintext bit. Being random bits hard to obtain in practice, the one-time pad is quickly dismissed and symmetric encryption schemes with short (and fixed-length) keys (aka block ciphers) are preferred.
Still, one popular mode of operation to encrypt long messages using block ciphers is essentially a one-time pad between plaintext and pseudo-random data that came out of a repeated application of the block cipher.

[cleverconcepts]

can you do a quick calculation of the probability of a plain text attack?