• We’re currently investigating an issue related to the forum theme and styling that is impacting page layout and visual formatting. The problem has been identified, and we are actively working on a resolution. There is no impact to user data or functionality, this is strictly a front-end display issue. We’ll post an update once the fix has been deployed. Thanks for your patience while we get this sorted.

Super Encyption Software

A

AncientMariner

Member
"Uncrackable encryption is allowing terrorists -- Hamas, Hezbollah, Al-Qaeda and others -- to communicate about their criminal intentions without fear of outside intrusion," former FBI Director Louis Freeh said last year before a Senate panel.


ummm..... i think we can crack this no? I've never heard of uncrackable encryption! You can always crack a prog.
i think these people are idiots!!! Where are our hackers when you need them???
 
Yes, everything is crackable by brute force, but it'd take way too long (hundreds of years) to try every key combination when the key is like 128bit in length. And over-encrypting (like Triple-DES etc) make it even worse by increasing the amount of possible combinations.

Lately, there has been some talk that Congress is going to require mandatory backdoors to be installed in every security software. I think that is unacceptable for a country that calls itself 'the land of the free', it's more like a police state.
 
The only uncrackable encryption is encryption based on Quantum Mechanics. It's, even in theory, impossible to decrypt this kind of encryption without the key.

[edit]: edited for clarification.
 


<< Where are our hackers when you need them??? >>



I believe most of the truly talented already work for the government.



<< Lately, there has been some talk that Congress is going to require mandatory backdoors to be installed in every security software >>



This would be *VERY* difficult to accomplish, unless we're talking about the consumption of this security software strictly from an end-user perspective. Many of the widely used ciphers (encryption algorithms) have reference implementations, which is the code used to implement the cipher itself. This could be analyzed for backdoors. It's hard to put a "backdoor" into a cipher purposely without those who scrutinize the cipher discovering it.

But again, if we're talking about the security software we see today for end-users, it would be simple to provide a means to recover the encrypted data if they were to implement a means to do so. This would essentially negate the entire idea of encryption, but hey, so long as the end-users are ignorant about it, it's ok, right? 🙂
 


<< Lately, there has been some talk that Congress is going to require mandatory backdoors to be installed in every security software. >>

Lately? This has been going on for a long time. Surely we all remember the ill-fated Clipper chip?
 
There is a company in Torrey Pines, CA (can't remember their name right now) that specializes in code breaking and the last I heard (many, many years ago) that the machines it was building for the govt. used some pretty heavy hardware decrypting (I also heard they were very good at what they do). I would guess that they have been doing their best to try and keep up with the encrypting technology. I would also guess they don't simply number crunch. I only basically understand true encrypting technology, so I really wouldn't be able to guess what is possible and what is not.

I think rather than trying to listen to every message going around the planet, just keep really close watch on people willing to associate themselves with a known terrorist and simply make it against international law to communicate at all with known terrorist sources. That way anyone willing to aid people that think harming innocents is an acceptable way of getting attention (I believe we give drugs to people with this problem or keep them locked up for their own safety and the safety of others) can and will be punished for even having been associated. If we are to have a safe and sane world then it is only reasonable to ask every country to partipate in not pandering to criminals. The world expects this from us, what would a country like Iraq think if we just decided to hate them to the point we felt extinction would be acceptable. Can you say a vast sea of glass? That would be real "terrorism". It has to start being a two way street where terrorism has to be considered a crime and those willing to associate themselves with these criminals need to be considered guilty by association. That means all of these festering holes of hate, need to be cleaned up. And considering the severity of the consequences when terrorists complete their missions, death should be the sentence.
 
Cracking good crypto is not possible via any known means. You can brute force it, but that isn't cracking it, that is just cracking a single message. Even then, you haven't cracked anything, you just tried everything possible until you got something that was human readable. To crack it would require figuring out an efficient way to find the factors of a number generated by multiplying two large prime numbers (where large typically indicates thousands of digits), when you only know one of the primes (the public key) and not the other prime, nor the product of the primes. Current best methods for well done crypto generally reduce the time to break from hundreds of millions of years or more to hundreds of millions of years times 0.95 or there-about.

RagManX
 
Lately, there has been some talk that Congress is going to require mandatory backdoors to be installed in every security software. I think that is unacceptable for a country that calls itself 'the land of the free', it's more like a police state. --if we are not careful about the changes we make after the terrorist attacks, we will be living in a police state sooner than we all think...that said, brute force decracking will never be much of an option because of the amount of time it takes...you must remember that these are messages, not software or a server just sitting static...
 


<< Cracking good crypto is not possible via any known means. You can brute force it, but that isn't cracking it, that is just cracking a single message. Even then, you haven't cracked anything, you just tried everything possible until you got something that was human readable. To crack it would require figuring out an efficient way to find the factors of a number generated by multiplying two large prime numbers (where large typically indicates thousands of digits), when you only know one of the primes (the public key) and not the other prime, nor the product of the primes. Current best methods for well done crypto generally reduce the time to break from hundreds of millions of years or more to hundreds of millions of years times 0.95 or there-about. >>



Some minor improvements:

1. Not all cyphers are based on factoring large numbers. In general they are based on operations that are easy to do (like multiplying two primes), but very hard to reverse (like factoring the result).

2. The example you give is the RSA encryption system, but in RSA the public key is the product of two large primes, not one of the primes.

3. Thousands of digit is a bit over the top. 128 bit encryption used a key of 128 bits 🙂, which in the decimal system corresponds to a number with way fewer than 100 digits.
 
That's not entirely true. There is unbreakable encryption, it just doesn't have the convenience that you're used to with public-key cryptography. Look into the one-time pad. Without the pad, it is unbreakable. Of course, you must exchange the pad beforehand, and it must only be used once.
 


<< The only uncrackable encryption is encryption based on Quantum Mechanics. It's, even in theory, impossible to decrypt this kind of encryption without the key.

[edit]: edited for clarification. >>




wow, got some linkage for some more reading?
 
I don't know if this is what khayyam meant, but (in theory) a random permutation of the alphabet generates an unbreakable code. In practice however, stochastical methods and data on appearance rates of certain characters and the fact that the encrypted message is usual in human readable form make it breakable.
 
There are certain ways to get 'around' those 'letter frequency of apperance analysis' by just making sure then you stuff up the input, with random letters, making it 'ONLY readable by humans'.

Such as the sentence

Hi, how are you.

before the message is encoded, alll you need to do is to put some random letters into every words. (but not so random such that the frequency of appearance is inversely biased what is 'expected'.

hie, hozw Pare y2oux.

Then encrpyting THIS, with a strong encrpytion, that is only 'crackable' by brute force, without knowing the original message is IMPOSSIBLE to crack.
 


<< 1. Not all cyphers are based on factoring large numbers. In general they are based on operations that are easy to do (like multiplying two primes), but very hard to reverse (like factoring the result). >>


True. I was thinking of asymetric cyphers, which to my knowledge are generally based on factor products of primes. Certainly the best known are. I was perhaps speaking a bit more generally than I should have, though. Point noted. 🙂



<< 2. The example you give is the RSA encryption system, but in RSA the public key is the product of two large primes, not one of the primes. >>


Yea, a stupid error on my part. Thank you for correctly pointing that out.



<< 3. Thousands of digit is a bit over the top. 128 bit encryption used a key of 128 bits , which in the decimal system corresponds to a number with way fewer than 100 digits. >>


Not sure why I said thousands of digits, when I intended thousands of bits (therefore hundreds of digits). Your 128 bit example is based on a shared secret symetric algorithm, though, correct? I don't know of any public key algorithm that does that few bits and offers reasonable security, and I don't believe any sensible user of crypto uses shared secret stuff for communication with many recipients. Already, users are being told 1024 bits minimum, 2048 preferred for PGP keys. Public key just gives away too much information to use shorter keys. Wish I could figure out where I've put my Applied Cryptography right now. I need to look some of this stuff up before I make more blatantly incorrect statements (hopefully I've not made any more this time)




<< By xtreme2k:
There are certain ways to get 'around' those 'letter frequency of apperance analysis' by just making sure then you stuff up the input, with random letters, making it 'ONLY readable by humans' >>



The problem with this is humans are terrible at generating random stuff, and this tends to lead to patterns that good crypto-crackers can pick up on and break. A true one-time pad with a good random source is, according to Schneier, unbreakable. The trouble is, finding a good random source is hard, which means not so good sources tend to get used, which means the message tends to get broken.

RagManX
 


<< Your 128 bit example is based on a shared secret symetric algorithm, though, correct? I don't know of any public key algorithm that does that few bits and offers reasonable security, and I don't believe any sensible user of crypto uses shared secret stuff for communication with many recipients. Already, users are being told 1024 bits minimum, 2048 preferred for PGP keys. Public key just gives away too much information to use shorter keys. >>



Well, RSA is a public key cypher and thousands of computer users are currently working together to crack a message that was encrypted with RSA using a 64 bit key. These are the current statisics for this challenge. According to this it would seem that 128 keys are vitually uncrackble for the forseable future.

128 bits ~ 3,4e+38 possible keys.

Lets say you can check 1,0e+14 keys per sec (ASCI white does 1,2e+13 ips), there are 100 secs in a minute, 100 minutes per hour, 100 hours per day and 1000 days per year, then it would still take 3,4e+15 years to crack one message, using a simple brute force algorithm.

[/EDIT] Oh, and the universe is approx. 1,5e+10 years old 🙂 [/EDIT]
 
My understanding of RSA, and the RC5-64 challenge differ from yours. Perhaps I need to do some more reading to be sure what is happening.

As I understand it, RSA is a combination shared secret and public key system. A message is encrypted with the shared secret key via RC5. The secret key is then encrypted using the recipients public key, attached to the encrypted message, and sent. The recipient decrypts the shared secret key using his/her private key, and then uses the shared secret key to decrypt the message.

The RC5-64 challenge is only brute forcing the symetric encryption portion of the RSA crypto system, which, like any symetric algorithm, is secure with relatively few bits.

According to The RSA FAQ, there is a set of RSA keys used, ranging from 576 to 2048 bits. These are different from the 40 to 256 bit RC5 key. My understanding of RSA leads me to believe that the public key portion of the system is these larger bit size keys. Also on the FAQ, RSA says that factoring 100 digit numbers is easy with modern hardware, but the factoring numbers of greater than 200 digits is not currently feasible. Further evidence that RC5 is just the symetric portion of the algorithm. With only 64 bits, the maximum value is 36893488147419103231, which should be easily factored, according the the RSA FAQ.

That's how I understand it, and until I can find my Applied Crypto, I can't check my recall of the algorithm any deeper than this. Let me know if I'm off here, and give me links to further reading if you would, so I can get a better grasp on the system.

BTW, I love this Highly Technical forum, even if I rarely can contribute...

RagManX
 
Trust me, installing those backdoors to 'strong' encrpytions are bloody stupid. Below is a quotation from /.

"72 percent of Americans believe that anti-encryption laws would be 'somewhat' or 'very' helpful in preventing a repeat of last week's terrorist attacks on New York's World Trade Center and the Pentagon in Washington, D.C." I realize that I'm preaching to the choir here, but it is scary how many people do not realize that the bad guys are not going to play fair here. Even granted that people may not realize the tools are already out there for the bad guys to use, I wonder what the polls will say when the backdoor gets compromised and 72% of people get their bank accounts wiped."

I find this so damn true. Those 72% of people prolly dont even know what encryption is really like anyway. Think if it this way. To 'help' the gove to track down terrorist, we install 'backdoors' to every house in the states, for every 'lock' installed, there has to be a backdoor to it. THEN i wonder how many people will 'agree' on that.

The fact is that we are ALL suffering now because the FBI/CIA has been lazy at their job. In my opinion, they all should be fired.
 
RagManX

What is that pad thing? Is there any links to it so that I can read more about it?

The 'random' thing I was talking about in my post is not all that random. What I mean was that say the letter E appears on most English words and they usually use that has a 'benchmark' to find the frequency of each letters. We fill the whole 'page' with such that the number of As = number of Bs = number of Cs.... etc etc or at least VERY SIMILAR numbers. Now, we have a totally balanced character frequency. Combine with SEVERAL encryption passes with DIFFERENT or the SAME encryption methods. It is totally unbreakable.

What happens is that you can also 'attach' other stuff ONTO the plain text to be encrypted, such as a voice recording and video and a picture. Encrypted with the method I mentioned above, it is impossible to crack.

Other options are 'keyless' encryptions. You pass the plaintext into a encypter that DOES NOT USE A KEY, it uses its own properitary encryption methods. Each 'party' has that program to use it to encrypt/decrypt that they share at the start. And there are certain undisclosed 'rules' that encryptions takes places and a 'lookup table' is used. Eg.
The first A is encrypted into *#<T#x, then maybe the 2nd A is encrypted 4gG#~, maybe the 3rd A you see in the plain text, it is encrypted into gjs%@... etc etc.... Here, you have basically a uncrackable encryption.

Yet another method came up to my head with this 'keyless' blackbox type encryption. Basically you convert the whole of the plain text as a massive binary matrix. And this program will 'rotate' the 0/1 of the matrix around in a properitary way, might want to inverse some of them, rotate some of them, move some of them in blocks....
 
In cryptography you operate with two different things regarding confidentiality: You can have unconditional security or computational security. Unconditional security means that the adversary does not have enough information to break it, even with infinite computing power, and computational security means that he does not have enough resources to break it. Unfortunately it's impossible to prove that any system provides computational security, and systems for unconditional security are not practical in real life. Since I sense that a lot of people are a bit confused about what encryption really is, here are some examples:

Unconditional security:

Any cipher (an algorithm for encryption/decryption) is said to be unconditionally secure if it provides perfect secrecy, which is defined as:

Pp(x) = Pp(x|y) for all plaintexts x and ciphertexts y

In words this means that the probability that plaintext x was sent is the same as the probability that plaintext x was sent given that you know the ciphertext y. Perhaps this might not make sense to some people, so I will not go further into this. If you think about it a little, it seems like a good definition.

The One-Time pad provides perfect secrecy. It works as follows. Write the data you want to encrypt (plaintext) in binary, eg:

10010101011101001

Now generate a key with the same number of bits as the plaintext where each bit is one with probability 0.5 and zero with probability 0.5. These key bits must be choosen independant of each other. Write that key below the plaintext:

10010101011101001 <- Plaintext
10100111010100101 <- Key

Now do a bitwise XOR of those to (XOR is addition modulo 2) - The XOR if two bits are 0 if the bits are equal and 1 if they're different

10010101011101001 <- Plaintext
10100111010100101 <- Key

00110010001001101 <- Ciphertext

The key must be used ONLY ONCE or you can easily break this. That's why it's called a ONE TIME pad

Why is this unbreakable? I could give a mathematical proof (it's pretty easy), but instead I will argue informally about this. Consider that for each bit of the plaintext it will be a 1 with probability 0.5 or a 0 with probability 0.5. Depending on how you select the key you can actually decrypt the ciphertext to anything you want. Therefore the ciphertext does not provide any information about the plaintext for those who does not have the key. Hope you can see this...

To decrypt just XOR the ciphertext with the key and you'll get the plaintext back (try it if you don't believe me 🙂

Of cause this is not practical. You need a key as large as the data you want to encrypt and that key can be used only once. If you have the ability to exchange the key in secrecy (you meet with the other person) why not give him the data instead.

Computational security:

It does not really have a formal definition, but you can't really prove that a system provides computational security. Some systems (eg. the RSA) can be proven computationally secure (you can give a lower bound on the computation time needed to break a message) GIVEN another problem (here factorization) is "difficult". I will not describe what difficult should mean, cause I would move over to complexity theory, and it might take a while to get back 🙂

There are two systems: Public key systems and private key systems (often called asymmetric and symmetric). In the former the same key is used to both encrypt and decrypt the data, whereas in the latter you use one key for encryption and one for decryption. You can publish you encryption key (the "Public Key") and only the private key can decrypt what's encrypted with the public key. The RSA is the most widely used system for this, but there are several others. I think a mathemathical description of the RSA would be too much here. If you really want to see it here, you can always ask and I might write it later.

Bottom line: All the systems you use in the real world SEEMS to provide computational security (although it can't be proven)

Quantum computation and quantum cryptography:

Since I'm following courses in both "Cryptography" and "Quantum Computation and Quantum Information" I will mention this briefly (and also because someone mentioned it earlier in this thread)

In a quantum computer you use the equivalent of a bit - a q-bit. These q-bits have the property that they can be either 1 or 0 or in a superposition where they are 0 with probability A and 1 with probaility B. Don't be mistaken they are NOT 1 or 0, but both at the same time. The trick is that is impossible to measure a q-bit without changing it's state. If you try to measure what state it is in, you'll get 0 with probability A and 1 with probability B. FURTHERMORE you will change the state to the result of your measurement. So if you measure it to be a 0 it IS a 0 and the same with 1. Also, it is impossible to copy a q-bit and you destroy it by measuring it.

Another feature difficult to understand is that you can place two q-bits in an "entangled" pair. In this state they are either both 0 with probability 0.5 or both 1 with probability 0.5. Here comes the hard part to understand. If you measure only the first q-bit and get a 0, you will also have changed the first q-bit to a 0, but since they were either both 0 or both 1, the second one WILL become 0 if you measure the first one to be 0. If you measure the first q-bit and get a 1 the second q-bit will be 1 too !!!

These properties allows you to perform 2^n computations SIMULTANEOUSLY with only n q-bits and will allow you to do weird things like finding the smallest element of an unsorted list of E elements by only looking at (square root of E) elements. It also allows you to break RSA (factor) in polynomial time. The problem is that not all problems can be expressed in a form that can be "understood" by a quantum computer. You might have guessed what the general problem is: Sure, you can do a lot of computations in parallel (actually you only do one computation that gives you ALL the possible results at once) but since you can't get get information out if a q-bit what good is this? Luckily there are ways to do this up a given probability.

Also this can be used for encryption that provides perfect secrecy. I will not go into details on how, but you can use the feature that you can't measure the state of a q-bit without destroying in. You can also have one person generating entangled pairs, teleporting one of the q-bits to the other person (yes, that can be done) and use these as part of the encryption (eg. for generating a completely random key for use in a one time pad). It's not as trivial as it sounds, but it can be done.

I have left out the physics part of this, since that would take too long to explain.

I could go on for a long time, but I will force myself to stop here. If you have further questions you can always ask.
 
No encryption is uncrackable. All the governement has to do is place a tap on your computer, watch your type in your password with a hidden camera, etc. As was shown last week, low tech can be used to defeat high tech.
 


<< RagManX
The 'random' thing I was talking about in my post is not all that random. What I mean was that say the letter E appears on most English words and they usually use that has a 'benchmark' to find the frequency of each letters. We fill the whole 'page' with such that the number of As = number of Bs = number of Cs.... etc etc or at least VERY SIMILAR numbers. Now, we have a totally balanced character frequency. Combine with SEVERAL encryption passes with DIFFERENT or the SAME encryption methods. It is totally unbreakable. >>



Be careful in what you say. There are several algorithms that provides a uniform distribution of the ciphertext letters that are easily broken. The simplest example is probably the Vigenere cipher, which can be broken by a ciphertext only attack. You make the mistake of considering only "ciphertext only" attacks, but there are other attacks too (known plaintext attack, choosen plaintext attack, choosen ciphertext attack).

Besides you need to specify what you mean by "SEVERAL encryption passes with DIFFERENT or the SAME encryption methods". If one of these encryption methods are the one time pad - yes it's secure. If they are all an insecure cipher, then your system is not secure.

Of cause it always helps decreasing the entropy of a message before encrypting it (eg. by compressing it first)
 


<< That's how I understand it, and until I can find my Applied Crypto, I can't check my recall of the algorithm any deeper than this. Let me know if I'm off here, and give me links to further reading if you would, so I can get a better grasp on the system. >>



You are right and I am wrong. In fact, RC5 has nothing to do with the standard RSA algorithm.

I did some reading on the subject myself (just got Introduction to Algorithms, 2nd Ed.) and I found out that we were both wrong on one point:

In RSA the public key is a combination of:
a) the product n of two large primes p and q.
b) an odd integer e that is relative prime to (p-1)(q-1).

And the secret key is the combination of:
a) the same product n
b) d, the multiplicative inverse of e, modulo (p-1)(q-1) (or: ed = 1 mod (p-1)(q-1))

After you calculate d and e, you should get rid of p and q.

The approximation I gave on the time required to crack a RC5-128 code is still valid it just has nothing to do with RSA.
Stupid of me to think that it is hard to factor a 128 bit number, my pocket calculator can do that 🙂
 
You must log in or register to reply here.

TRENDING THREADS

Back
Top