PDA

View Full Version : My Encryption Algorithm...



Junior89
07-24-2007, 11:13 PM
Well i couldn't seem to find a good forum (out there on the web) or anything like that for a little review and courteous criticism of my algorithm here. I'm sure it's stupid and insecure but i would like it if someone with some knowledge in the field could point out some of the biggest mistakes i made. I'm not naive and i do know that it probably isn't more than a dressed up XOR encryption but hey, i'll give it a shot!

whiteflags
07-25-2007, 02:02 AM
Well what I do know about xor encryption - which is what your algorithm builds off of - xor encryption seems to work better with (much) longer and significantly random keys. I think that dividing the work and applying xor's to only parts of it is probably wrong, or at least a mistake. So that's something to really think about.

As far as making the encryption stronger, well, most modern algorithms work with hashes and randomness for a reason. Regardless of the strength you're looking for, the permutation step can do so much more than it is right now. Do better than shifting by a constant. I don't find the cyclic approach very clever either, but that's largely an uncomfortable opinion of mine. Think about that too; it should be well disguised if it is to be part of a strong algorithm.

The moral when it comes to cryptography I think, while not something that I've studied in great detail, is that you want to avoid giving crackers really stupid hints. It's better to give a cracker an entire, well-designed prng to crack than coincidentally having 0xA as the first bit to every key, or something, because you've generated small, repetitious keys.

abachler
07-26-2007, 09:38 AM
Modern cryptoghraphy makes minimal use of XOR. Most of it is based off the Diffy/Hellman/Merkle algorithm using large( >256 bit) prime numbers. Even LSFR are old hat, since you can crack them in polynomial time. Check out this (http://en.wikipedia.org/wiki/Diffie_hellman) for a decent description of the process.

laserlight
07-26-2007, 09:48 AM
Modern cryptoghraphy makes minimal use of XOR. Most of it is based off the Diffy/Hellman/Merkle algorithm using large( >256 bit) prime numbers.
That sounds more applicable to public cryptography to me, where the keys would be more likely be 1024 bits or larger primes (or probable primes). For example, I think Twofish uses XOR quite extensively.

brewbuck
07-26-2007, 10:37 AM
Modern cryptoghraphy makes minimal use of XOR. Most of it is based off the Diffy/Hellman/Merkle algorithm using large( >256 bit) prime numbers. Even LSFR are old hat, since you can crack them in polynomial time. Check out this (http://en.wikipedia.org/wiki/Diffie_hellman) for a decent description of the process.

The majority of encrypted data in the world is encrypted with XOR. Specifically, the plaintext stream is XOR'd with a key stream generated by a streaming cipher, initialized with a key that is communicated securely via some public key cipher using appropriate protocols.

Encryption using large primes is incredibly slow. It is only used to establish a secure channel for key exchange, or for signature validation.

abachler
07-26-2007, 10:53 AM
Encryption using large primes is incredibly slow.
while million digit primes require about an hour to encrypt with, more reasonably sized primes, such as 64k digit primes take sub-millisecond times. With high speed encryption routines, the final encryption can take as little as 1uS.


It is only used to establish a secure channel for key exchange, or for signature validation.

That is incorrect, perhaps it is only used for that purpose in consumer applications.

brewbuck
07-26-2007, 11:12 AM
That is incorrect, perhaps it is only used for that purpose in consumer applications.

What other application would I be talking about? Obviously there are special purpose systems of all kinds, out there.

My point is that most encryption users are familiar with (SSL) is not based on primes.

laserlight
07-26-2007, 11:12 AM
while million digit primes require about an hour to encrypt with, more reasonably sized primes, such as 64k digit primes take sub-millisecond times. With high speed encryption routines, the final encryption can take as little as 1uS.
Would not such small primes become a weakness (e.g., allowing brute force attacks)?


That is incorrect, perhaps it is only used for that purpose in consumer applications.
I do not know if the U.S. government uses public key cryptography for more than things like key exchange, but I do know that AES (a symmetric cipher) was approved for use on U.S. government documents, even those at top secret level. Keystream generation aside, even AES uses XOR rather extensively.

abachler
07-26-2007, 11:57 AM
public key cryptography based on the DHM key exchange protocol is a solved problem. Its not secure. The only measure of security it provides is the processing requirements needed to reverse the key exchange using only the public data. At least with publicly available methods. Because the process is deterministic, mathematical theory states that there must exist an algorithm that would make cracking public keys trivial. I wouldnt trust my recipe for chili to AES, let alone my IP...

As for the govt, maybe congress and the FBI use AES, but I guarantee you that the military/NSA/CIA/HLS do NOT use public key exchange in any way shape or form.

64k digit primes (65536 bit) are significantly non-trivial to crack. Even AES 256 and 512, which use 256 bit and 512 bit primes respectively, are non-trivial using public methods.

laserlight
07-26-2007, 12:03 PM
public key cryptography based on the DHM key exchange protocol is a solved problem. Its not secure. The only measure of security it provides is the processing requirements needed to reverse the key exchange using only the public data. At least with publicly available methods.
Of course, there is the caveat of "current and near future technology", otherwise quantum computing and the like would make "complexity theoretic" cryptography obsolete. In that sense, I would argue that it is secure. After all, a locked door is secure, but not when you have a fire axe to break it down.


I wouldnt trust my recipe for chili to AES, let alone my IP...
Why? What about the other AES finalists?

QuestionC
07-26-2007, 12:06 PM
Modern cryptoghraphy makes minimal use of XOR. Most of it is based off the Diffy/Hellman/Merkle algorithm using large( >256 bit) prime numbers. Even LSFR are old hat, since you can crack them in polynomial time. Check out this (http://en.wikipedia.org/wiki/Diffie_hellman) for a decent description of the process.

This is simply not true. Private Key encryption algorithms use XOR all over the place. I'm not talking one-time pad here.. I'm talking DES, Blowfish, AES.

brewbuck
07-26-2007, 12:13 PM
public key cryptography based on the DHM key exchange protocol is a solved problem. Its not secure. The only measure of security it provides is the processing requirements needed to reverse the key exchange using only the public data. At least with publicly available methods. Because the process is deterministic, mathematical theory states that there must exist an algorithm that would make cracking public keys trivial. I wouldnt trust my recipe for chili to AES, let alone my IP...

With that comment, I'm pretty sure now that you have no idea what you're talking about.

abachler
07-26-2007, 12:18 PM
This is simply not true. Private Key encryption algorithms use XOR all over the place. I'm not talking one-time pad here.. I'm talking DES, Blowfish, AES.

DES - cracked on a circa 1985 desktop ($1000)
Triple DES - cracked on a circa 1995 cluster ($10,000)
Blowfish - intentionally so weak it was cracked before full implementation
AES - cracked, at least by the NSA

and we arent talking about private key encryption, we were talking public key encryption. In general during private key encryption, the use of XOR is less as an encryption method, and more as an optimization method for speeding up large scale modulus operations.


With that comment, I'm pretty sure now that you have no idea what you're talking about.
That statement is beneath contempt.

laserlight
07-26-2007, 12:29 PM
and we arent talking about private key encryption, we were talking public key encryption. In general during private key encryption, the use of XOR is less as an encryption method, and more as an optimization method for speeding up large scale modulus operations.
No, we are talking about "modern cryptography". If you wanted to talk about public key encryption, then you should have said so, but Junior89's algorithm clearly is not public key cryptography.


Blowfish - intentionally so weak it was cracked before full implementation
As far as I know, there is no attack on Blowfish faster than brute force. Perhaps you are confusing attacks on a reduced round Blowfish?


AES - cracked, at least by the NSA

I guarantee you that the military/NSA/CIA/HLS do NOT use public key exchange in any way shape or form.

Even AES 256 and 512, which use 256 bit and 512 bit primes respectively, are non-trivial using public methods.
Those are... incredible claims. The first two may be true, but I find no evidence for the latter. What are these "public methods" that you speak of? In fact, since when was there 512 bit AES?


64k digit primes (65536 bit) are significantly non-trivial to crack.
Ah, I misread you, I was thinking of numbers in the magnitude of 64000. Looks like you mean "64K bit primes". 64K digit numbers are in the range of 200K bits, which would mean both of us would be wrong :p
I agree that 64K bit keys would be far more than enough security, since I never heard of anyone other than snake oil recommending more than 2K bit keys. Still, the times that you cite sound more like those of a supercomputer than ordinary desktops.

abachler
07-26-2007, 01:00 PM
If you wanted to talk about public key encryption
Yes, we are talkling modern crypto, but all crypto can be broken into the two categories public or private key. Since the statements were about public key, I felt it appropriate to illuminate this fact when replying to a comment that changed the discussion from public key to private key in order to attempt to refute a statement made about public key crypto.


As far as I know, there is no attack on Blowfish faster than brute force. Perhaps you are confusing attacks on a reduced round Blowfish?
While I provided a link to wikipedia to the original poster, that does not mean I advocate wikipedia as the supreme authority on all things crypto. Blowfish is a running joke in professional crypto circles. Strong enough to avoid cracking on a home computer, but trivial to crack by a foreign power.



Those are... incredible claims. The first two may be true, but I find no evidence for the latter. What are these "public methods" that you speak of? In fact, since when was there 512 bit AES?

Last I checked you get AES-512 on thumbdrive encryption utilities.

laserlight
07-26-2007, 01:13 PM
Since the statements were about public key, I felt it appropriate to illuminate this fact when replying to a comment that changed the discussion from public key to private key in order to attempt to refute a statement made about public key crypto.
Sounds like a misunderstanding. You were the first one to mention public key cryptography in this thread. citizen's comments were directly concerning Junior89's algorithm.


While I provided a link to wikipedia to the original poster, that does not mean I advocate wikipedia as the supreme authority on all things crypto.
Please do not make such assumptions, unless you wish your own statements to be "beneath contempt" :p
I did not use Wikipedia as an authority here, though I did use it as a reference to double check. Schneier's website on Blowfish claims: "Vincent Rijmen's Ph.D. thesis includes a second-order differential attack on 4-round Blowfish that cannot be extended to more rounds."


Last I checked you get AES-512 on thumbdrive encryption utilities.
FIPS 197 (http://csrc.nist.gov/publications/fips/fips197/fips-197.pdf) states: "The AES algorithm is capable of using cryptographic keys of 128, 192, and 256 bits to encrypt and decrypt data in blocks of 128 bits."
There is clearly no mention of 512 bit keys. I had the impression that primes are not needed for keys in symmetric ciphers.

QuestionC
07-26-2007, 03:53 PM
Well i couldn't seem to find a good forum (out there on the web) or anything like that for a little review and courteous criticism of my algorithm here. I'm sure it's stupid and insecure but i would like it if someone with some knowledge in the field could point out some of the biggest mistakes i made. I'm not naive and i do know that it probably isn't more than a dressed up XOR encryption but hey, i'll give it a shot!

Block 1...


a, b, c, d
a^L, b^L, c^L, d^L
d^L, a^L, b^L, c^L
d^L^R, a^L^R, b^L^R, c^L^R
S(d^L^R), S(a^L^R), S(b^L^R), S(c^L^R)

We can undo the S(), so it's just a problem of finding L^R, which is just a single XOR problem. Cracking XOR of plaintext is a problem solved long ago.


On the other hand, look at block 3...


a, b, c, d
a^R, b^R, c^R, d^R
S(a^R), S(b^R), S(c^R), S(d^R)
S(a^R)^L, S(b^R)^L, S(c^R)^L, S(d^R)^L
S(d^R)^L, S(a^R)^L, S(b^R)^L, S(c^R)^L

This is better, because L^R can't combine into a single XOR problem. The classic XOR methodology wouldn't work.



To be honest, the biggest problems with this are...
1) The permutation method is far too simple.
2) It doesn't repeat enough times.

I suggest trying to implement a Feistel cipher (http://en.wikipedia.org/wiki/Feistel), what you have is very close to that, which is the basis of a lot of cryptography.