I am trying to modify the existing code on the forums (the RC4Mem procedure by Pille from the link below) to obtain RC4A, an improved version of this stream cipher. Like its predecessor, this algo has some weaknesses, but not that critical.
http://www.purebasic.fr/english/viewtop ... hlight=rc4
The whitepaper i tried to use is available here:
http://etd.uwaterloo.ca/etd/memckagu2005.pdf
Can anyone give me a kickstart with this?
Help implementing RC4A (better RC4)
Help implementing RC4A (better RC4)
None are more hopelessly enslaved than those who falsely believe they are free. (Goethe)
-
UserOfPure
- Enthusiast
- Posts: 469
- Joined: Sun Mar 16, 2008 9:18 am
Re: Help implementing RC4A (better RC4)
I would like to see RC4 added to the Cipher library. Strange that it hasn't so far.
I guess it could be added, but I'm not sure the team thinks that the implementation is correct enough. And if the PB team adds it, I'm sure people will want some other algos implemented too 
. Not a bad idea though.
. Not a bad idea though.None are more hopelessly enslaved than those who falsely believe they are free. (Goethe)
-
UserOfPure
- Enthusiast
- Posts: 469
- Joined: Sun Mar 16, 2008 9:18 am
I did this some time ago: http://www.purebasic.fr/english/viewtopic.php?t=14044
A very clever combination of MD5 and ARCFOUR.
If you are just interested in ARCFOUR (and compatible with RC4) try to dig up Friedhelm's improvement on Pille's code.
Not sure if Friedhelm's has the extra iteration/permutations as I added at the start that get's around one of the weaknesses of ARCFOUR or RC4.
A very clever combination of MD5 and ARCFOUR.
If you are just interested in ARCFOUR (and compatible with RC4) try to dig up Friedhelm's improvement on Pille's code.
Not sure if Friedhelm's has the extra iteration/permutations as I added at the start that get's around one of the weaknesses of ARCFOUR or RC4.
Hi Rescator, thanks for the link . I'll have a look at it.
The extra permutations seem to be a very necessary thing if we plan to use this algorithm nowdays. Without them it seems that it can be killed in very short time.
. I'll have a look at it. The extra permutations seem to be a very necessary thing if we plan to use this algorithm nowdays. Without them it seems that it can be killed in very short time.
None are more hopelessly enslaved than those who falsely believe they are free. (Goethe)
Funny thing about the RC4 weakness.
It was used in the initial WiFi protocols, and since WiFi sends the same packets over and over, the weakness of RC4 in those initial permutations was part of the reason WiFi was cracked.
The improved WiFi protocols added some iterations to the start of the RC4 stream before actually using it.
Kinda like letting a motor run to "get it warmed up" in the winter I guess
After that RC4 (or ARCFOUR as the open source variant is called due to RC4 being a trademark) is pretty solid.
Most good stream ciphers (like RC4) is twice as good as a block cipher at the same key bit size. So a stream cipher at 1024bits is as secure as a block cipher at 2048bits.
A stream cipher also has the benefit of not needing any padding like block ciphers do.
And if a single byte in the stream is wrong then the rest of the stream is useless, whereas block ciphers recover at the next block. I consider this a security feature really and why I like stream ciphers so much
The down side is that a stream cipher need to resend all data if it's corrupted. BUT you can easily add your own block and checksum wrapper and send the stream is blocks yourself, getting the best of two worlds I guess
I'm gonna read through that paper but I doubt I'll attempt to make ARCFOUR-A or -B or -C or -whatever in the nearest future. (if nobody makes one I might end up doing one though)
The code in my post I mentioned earlier is quite optimized and should be one of the fastest ones on these forums (unless a ASM one is lurking around I haven't noticed) and hopefully a nice starting point.
Wikipedia might be a nice starting point too, but considering this will be a modified/enhanced ARCFOUR maybe one should not call it exactly that as it's not stream compatible with ARCFOUR or RC4.
But I find something like a improved ARCFOUR a must, we got MD5 and combine that with ARCFOUR and you got some quick (very quick actually) hash and encrypt combo.
PS! In my code I iterate/permutate a few times before actually encrypting the data, it may be possible to just use a optimized standard ARCFOUR and simply feed it x amount of binary 0's at the start to get the same permutation iterations. But don't take my word for that though, study the stuff out there describing the weakness and how to avoid it. It's a while since I last read up on this and I could be mistaken.
But if you simply can add on some throwaway data at the start then the standard ARCFOUR could be implemented as is (with a big warning in the documentation to add some throwaway data at the start I guess) thereby retaining stream compatibility.
With a good password (and my post earlier shows how to make a pass longer while avoiding making it weaker, in fact it gets a bit stronger even) ARCFOUR should be adequate for general encryption use just like MD5 is adequate for general hashing and CRC32 is adequate for general checksums. So a nice team of quick code implementations.
If no weaknesses are introduced in the implementation then it should be enough to protect your average data. (if you are worried about computer slave cracking farms or super computer cracking then the data you are worried about need close to military grade encryption anyway) ARCFOUR data encrypted with the extra startup iterations and a good password (combined with the expanding MD5 tip in my post) should keep the data safe for maybe a decade or two, to protect the password further I guess you could even mix the pass or concatenate with the date and filename as well to avoid compromising the password in case a single file manages to be cracked a few years later.
What I'm saying is that ARCFOUR itself, while it has a few flaws, those flaws are known and can be avoided. Other than that it is time tested and solid and not weak in and of it self. So using it as the core and instead enhancing it by pre-processing the password and even the data (and don't forget those extra empty permutations at the start) not only keeps the tested integrity of the original but improves it further.
As soon as you start altering the actual ARCFOUR stream code etc. All bets are off and it can be easy to leave a huge weakness open.
Just ask all those that did their own stream ciphers only to realize thir clever Xor did not handle binary 0 so well and bin 0 would reveal the password. Oops!
At least ARCFOUR is solid, which is very important. MD5 is solid as well despite a few collision hits, but it's still solid.
Minirant (and why I like MD5 and RC4): How scientists can expect to get a perfect hash or checksum is beyond me, the only way to get a perfect one with 0% chances of collisions is if the checksum result itself is as large as the file it's checksumming. *laughs*
And as far as encryption goes, the only truly safe encryptions are "One Time Pad" based ones with insanely huge key bit sizes. It is more important to delay or disinterest any "evil" people long enough until that data you transfered is no longer valid or outdated and thus no longer sensitive. Safe for 1000 years? Overkill. a few decades? Fie I guess. Imagine encrypting source code, do you believe that todays source code would even matter 10-20 years from now?
*laughs*
It was used in the initial WiFi protocols, and since WiFi sends the same packets over and over, the weakness of RC4 in those initial permutations was part of the reason WiFi was cracked.
The improved WiFi protocols added some iterations to the start of the RC4 stream before actually using it.
Kinda like letting a motor run to "get it warmed up" in the winter I guess
After that RC4 (or ARCFOUR as the open source variant is called due to RC4 being a trademark) is pretty solid.
Most good stream ciphers (like RC4) is twice as good as a block cipher at the same key bit size. So a stream cipher at 1024bits is as secure as a block cipher at 2048bits.
A stream cipher also has the benefit of not needing any padding like block ciphers do.
And if a single byte in the stream is wrong then the rest of the stream is useless, whereas block ciphers recover at the next block. I consider this a security feature really and why I like stream ciphers so much
The down side is that a stream cipher need to resend all data if it's corrupted. BUT you can easily add your own block and checksum wrapper and send the stream is blocks yourself, getting the best of two worlds I guess
I'm gonna read through that paper but I doubt I'll attempt to make ARCFOUR-A or -B or -C or -whatever in the nearest future. (if nobody makes one I might end up doing one though)
The code in my post I mentioned earlier is quite optimized and should be one of the fastest ones on these forums (unless a ASM one is lurking around I haven't noticed) and hopefully a nice starting point.
Wikipedia might be a nice starting point too, but considering this will be a modified/enhanced ARCFOUR maybe one should not call it exactly that as it's not stream compatible with ARCFOUR or RC4.
But I find something like a improved ARCFOUR a must, we got MD5 and combine that with ARCFOUR and you got some quick (very quick actually) hash and encrypt combo.
PS! In my code I iterate/permutate a few times before actually encrypting the data, it may be possible to just use a optimized standard ARCFOUR and simply feed it x amount of binary 0's at the start to get the same permutation iterations. But don't take my word for that though, study the stuff out there describing the weakness and how to avoid it. It's a while since I last read up on this and I could be mistaken.
But if you simply can add on some throwaway data at the start then the standard ARCFOUR could be implemented as is (with a big warning in the documentation to add some throwaway data at the start I guess) thereby retaining stream compatibility.
With a good password (and my post earlier shows how to make a pass longer while avoiding making it weaker, in fact it gets a bit stronger even) ARCFOUR should be adequate for general encryption use just like MD5 is adequate for general hashing and CRC32 is adequate for general checksums. So a nice team of quick code implementations.
If no weaknesses are introduced in the implementation then it should be enough to protect your average data. (if you are worried about computer slave cracking farms or super computer cracking then the data you are worried about need close to military grade encryption anyway) ARCFOUR data encrypted with the extra startup iterations and a good password (combined with the expanding MD5 tip in my post) should keep the data safe for maybe a decade or two, to protect the password further I guess you could even mix the pass or concatenate with the date and filename as well to avoid compromising the password in case a single file manages to be cracked a few years later.
What I'm saying is that ARCFOUR itself, while it has a few flaws, those flaws are known and can be avoided. Other than that it is time tested and solid and not weak in and of it self. So using it as the core and instead enhancing it by pre-processing the password and even the data (and don't forget those extra empty permutations at the start) not only keeps the tested integrity of the original but improves it further.
As soon as you start altering the actual ARCFOUR stream code etc. All bets are off and it can be easy to leave a huge weakness open.
Just ask all those that did their own stream ciphers only to realize thir clever Xor did not handle binary 0 so well and bin 0 would reveal the password. Oops!
At least ARCFOUR is solid, which is very important. MD5 is solid as well despite a few collision hits, but it's still solid.
Minirant (and why I like MD5 and RC4): How scientists can expect to get a perfect hash or checksum is beyond me, the only way to get a perfect one with 0% chances of collisions is if the checksum result itself is as large as the file it's checksumming. *laughs*
And as far as encryption goes, the only truly safe encryptions are "One Time Pad" based ones with insanely huge key bit sizes. It is more important to delay or disinterest any "evil" people long enough until that data you transfered is no longer valid or outdated and thus no longer sensitive. Safe for 1000 years? Overkill. a few decades? Fie I guess. Imagine encrypting source code, do you believe that todays source code would even matter 10-20 years from now?
*laughs*
@Rescator, you are definitely right. I for one always liked RC4 because it was darn simple and still offers pretty decent protection. And if it were to encrypt something so it can't be decrypted, i'd better memorize it... With the technology today it would get decrypted in a way or another. Not to mention in a few years... But fortunately what I want to use it for will just guard personal data, not military secrets .
About the PRNG of RC4, i think the best to do would be to drop the first 65536 bytes (it's called "ARC4-drop[65536]" AFAIK). This should get the internal state very random.
I will try to play a bit with this and if I get it to work, i'll post the result here.
@Trond,
Bah... Nothing made by humans is ever safe. There will always be somebody to try and break what others did.
.About the PRNG of RC4, i think the best to do would be to drop the first 65536 bytes (it's called "ARC4-drop[65536]" AFAIK). This should get the internal state very random.
Yes, that is a pain in the arse... One wrong step and bam!A stream cipher also has the benefit of not needing any padding like block ciphers do.
They can't. This is not possible. But they can try to minimize the collision rate at their best.Minirant (and why I like MD5 and RC4): How scientists can expect to get a perfect hash or checksum is beyond me, the only way to get a perfect one with 0% chances of collisions is if the checksum result itself is as large as the file it's checksumming. *laughs*
I will try to play a bit with this and if I get it to work, i'll post the result here.
@Trond,
Bah... Nothing made by humans is ever safe. There will always be somebody to try and break what others did
.None are more hopelessly enslaved than those who falsely believe they are free. (Goethe)
-
Joakim Christiansen
- Addict
- Posts: 2452
- Joined: Wed Dec 22, 2004 4:12 pm
- Location: Norway
- Contact:
Actually 100% safe encryption can be made: (but it might not stay safe in the future)Trond wrote:When quantum encryption arrives it's supposed to be safe, but I'm telling you, it won't be.And as far as encryption goes, the only truly safe encryptions are "One Time Pad" based ones with insanely huge key bit sizes.
http://www.cebaf.gov/news/internet/1997/spooky.html
Read the whole article, it's damn interesting. Actually I bet twin protons can be used for data-transfer faster than light too, I'm sure we will have it some day, but that's just me, I'm weird"This research is interesting not only from a scientific and philosophical point of view, but because of a very practical consequence: we can now create a completely secure code. A quantum key, which is now within reach, would allow banks to carry out transactions with each other over optical fibers, completely safe from all possible code-breaking methods and from eavesdropping or interference."
The idea for such a system, he said, originated with Dr. Artur D. Eckert at Oxford University in England.
Details of the Swiss experiment will be described in a forthcoming technical paper, Gisin said, and he is working with the Swiss telecommunications agency to develop a cryptographic system based on entangled particle "twins." Identical random-number sequences generated simultaneously by pairs of widely separated twins would serve as cipher keys equivalent to the "one-time pads" used by spies and governments to encode and decode ultra-secret messages.
Sorry Inf0Byt3 for being off-topic now...
I like logic, hence I dislike humans but love computers.
I mean "normal" quantum encryption without any twins, but with the use of photons to make a secret key. See part 5 here: http://www.cs.dartmouth.edu/~jford/crypto.html
What supposedly makes it safe is that it's impossible to listen to the communication without destroying it. However, that's not a problem as long as neither the reciever nor the sender notices that the communication is destroyed.
What makes it crackable is that Bob needs a way to decode it. All Eve has to do is:
A. Mask herself as Bob, and as Alice is concerned, act exactly like Bob
B. Prevent anything sent from Alice to ever reach Bob
C. Mask herself as Alice, and as Bob is concerned, act exactly like Alice.
D. Prevent anything sent from Bob to ever Alice
So when Alice thinks she is negotigating with Bob to find a private key, she is in reality negotigating with Eve.
At the same time, Bob thinks he is negotaing with Alice, but in reality, he's negoting with Eve as well.
The result is that both Bob and Alice now thinks they have one private key. In reality, they have two different keys, and Eve has both.
What supposedly makes it safe is that it's impossible to listen to the communication without destroying it. However, that's not a problem as long as neither the reciever nor the sender notices that the communication is destroyed.
What makes it crackable is that Bob needs a way to decode it. All Eve has to do is:
A. Mask herself as Bob, and as Alice is concerned, act exactly like Bob
B. Prevent anything sent from Alice to ever reach Bob
C. Mask herself as Alice, and as Bob is concerned, act exactly like Alice.
D. Prevent anything sent from Bob to ever Alice
So when Alice thinks she is negotigating with Bob to find a private key, she is in reality negotigating with Eve.
At the same time, Bob thinks he is negotaing with Alice, but in reality, he's negoting with Eve as well.
The result is that both Bob and Alice now thinks they have one private key. In reality, they have two different keys, and Eve has both.
http://en.wikipedia.org/wiki/One_time_pad
One time pads are the only known 100% crack proof encryption I believe.
They are somewhat inconvenient though and any tweaks you make in an attempt to be a more useful type of encryption (like using a PRNG etc) means it's not 100% anymore.
One time pads are the only known 100% crack proof encryption I believe.
They are somewhat inconvenient though and any tweaks you make in an attempt to be a more useful type of encryption (like using a PRNG etc) means it's not 100% anymore.
Paul Dwyer
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein
“In nature, it’s not the strongest nor the most intelligent who survives. It’s the most adaptable to change” - Charles Darwin
“If you can't explain it to a six-year old you really don't understand it yourself.” - Albert Einstein