×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

When Pretty Good Privacy Isn't Good Enough

Roblimo posted more than 14 years ago | from the let's-not-confuse-codes-with-ciphers dept.

Encryption 169

st. augustine writes "Worried that the NSA already knows how to crack PGP? Someone calling themselves Hardened Criminal Software has a one-time pad package called HardEncrypt that could be the answer to your paranoia. The sci.crypt Snake Oil FAQ teaches us to beware of one-time pad claims, but it looks like Hardened Criminal has done their homework. No bogus bit-stream algorithms or pseudo-random number generators. And it's open-source, so everyone can bang on it and fix any problems. I'd try it myself, but I'm outside the US, and the Bernstein decision doesn't apply in New York. :-)"

cancel ×
This is a preview of your comment

No Comment Title Entered

Anonymous Coward 1 minute ago

No Comment Entered

169 comments

Close (1)

zCyl (14362) | more than 14 years ago | (#1733606)

You gain a lot of efficiency when trying to factor large numbers if you give up at sqr(N). There's no reason to go the whole way to N/2, as you would just be duplicating your efforts.

Re:Looks OK, but the problem with 1-time pads is.. (0)

Anonymous Coward | more than 14 years ago | (#1733607)

Some practical thoughts:
"You can never use the same key for more than a single message."
(a) Drawing randomly from a very large pool of keys assures that, unless your antagonist is very organized, you're likely to be secure. Even if she is organized, you should not be on her radar.

"It's a secret key algorithm, which means that sending the message to someone else requires that you get the key to them somehow."
(b) Unless there are a lot of random keys available in a widespread (physical) public medium. Then all you need is a (previously-agreed) list, not data. This requires forethought, not suitable to everyone.

"key storage is a problem."
See (b)

This code is trash. DO NOT USE IT. (1)

Convergence (64135) | more than 14 years ago | (#1733608)

Yes, its dependent on the fact that a given pad is only used once. But whats more important is that the pad is unpredictable. If I create successive 1024-bit pieces of the pad by counting up in binary. using a 1024-bit wordsize, and I start at a 'random number', I will not use the same key twice, but the key is predictable, and so its bad.

In their case, its trash, there are very very few fast ways of generating such pads, The only convinenent one I can think of is /dev/random, which is about 20-100 bits a second. Since they are not using any of the right techniques, they are doing it wrong.

Using OTP is easy, whats hard is generating the pad and getting it to the other recipient.

Doesn't use real one-time pad (1)

mesocyclone (80188) | more than 14 years ago | (#1733619)

The encryption scheme, claimed as "unbreakable", in fact is subject to very standard cracking techniques. One time key schemes have been broken many times - by attacking the source of the one time pad. For example, historical schemes have used paragraphs from obscure books. Attacks consist of: (1) looking for the paragraph, or (2) using the non-randomness (low entropy) of human language to statistically crack the code.

The latter approach should work pretty well with an audio source (a sound card is used by the programs describe). Audio is usually highly non-random. It depends on what is connected to the audio board. If it is environmental noise, it will probably have certain frequencies emphasized. If it is music, it is already highly structured (except, perhaps, for certain modern rock "music" which seems to me to be almost flat spectrum :-). Voice is likewise highly structured.

Given that the authors claim it is unbreakable, I would immediately suspect that they are cryptographic novices, and thus be suspicious of the details of their algorithms in addition to their poor choice of randomness.

If they had used a semirandom source (like audio or key click timings or something), and THEN used a solid cypher to encrypt it to produce the one-time key, I would be much happier.

The Value of OTP (1)

TheDullBlade (28998) | more than 14 years ago | (#1733620)

People are complaining about how useless OTP is, but it does have some extremely valuable uses.

After an initial secure communication of random bytes, you can send the same amount of data over insecure communication routes in absolutely perfect security.

Think of it; if you sent a CD-Rs of random noise to a friend, you could probably email securely with him for the rest of your life. Nobody could ever crack it, no matter how many billions of dollars worth of computer equipment, no matter how much computers improve, no matter how many millenia they spend on it. If you both deleted the used key data after communicating, and he deleted the message after reading it, nobody could ever know what you told him, even if your computers were seized.

Other reversible encryption schemes merely make it hard to decrypt a message. A large government agency with sufficient resources might do it, or a distributed effort, or a new computing technology might make it cheap and simple. If you encrypt and communicate something that can be damaging to you even 20 years in the future, it will hang over your head like the sword of Damocles for the rest of your life, unless you used OTP.

Any reversible data encryption requires that you use an inherently secure communication channel to send a key to the recipient before you can use insecure channels to securely communicate with him. It's just that in this case the key is large and can get used up. Since the only really inherently secure communication channel is handing someone a disk with the data, why bother with a short key? Disks are cheap, give him a few gigabytes of OTP and be perfectly secure.

Re:Why people don't use one time pads (1)

Sun Tzu (41522) | more than 14 years ago | (#1733621)

hmmm... is your first string...

"j=`K~8v]-2.D:&.6*i$_kQ\?,|)dE" by any chance?

No? Ok... must be a bug in my algorithm... ;)

Not a very accurate exp. of Prime factorization (0)

Anonymous Coward | more than 14 years ago | (#1733622)

From the docs:
>As of right now, all known algorithms for prime number factorization
>are quite slow. They are all reducible to an algorithm that tries
>every possible factor. So, given a large number N, if you know that N
>has two factors, you can find them by trying to divide N by every
>number up to N/2. You'll eventually find one of N's two factors
>this way, and after dividing, you'll have found the other as well.
>But, there's nothing to say that you won't have to try all possible
>factors, and there are N/2 of them, so running time of the
>algorithm is proportional to N, or the size of the number you're
>trying to factor. To make the encryption keys harder to crack,
>you simply use a larger N.
>
> A running time of N doesn't seem bad (seems polynomial).
>However, if you look at the problem as one that takes N as input in
>binary form, and N is represented by X binary digits, then the
>running time of the algorithm is really 2^X, or exponential in the
>input size.

Well, it's not quite as simple as they put forth here. First off, you don't need to search 1...N for factors to N. 2...sqrt(N) is sufficient. If you aven't found a factor by then, you won't find one at all.

Second, using a sieve of Erastosthenes (sp?) you don't have to evaluate every number between 2...sqrt(N). You just test all the PRIMES between 2...sqrt(N). For example, if you know that 2 is not a factor, then 4 obviously can't be either.

This is not to say that the algorithm isn't exponentially bounded, just that it isn't quite as bad as they make it out to be. Not to mention that it's impossible to evaluate the run time of something like that because it's dependent on the number of primes between 2 and the square root of N.

Bart "too lazy to set up an account" Grantham

Their math is wrong. (1)

Nathaniel (2984) | more than 14 years ago | (#1733623)

Among the errors on their W hy it's uncrackable [cornell.edu] page is this bit:
So, given a large number N, if you know that N has two factors, you can find them by trying to divide N by every number up to N/2. You'll eventually find one of N's two factors this way, and after dividing, you'll have found the other as well. But, there's nothing to say that you won't have to try all possible factors, and there are N/2 of them...

First: You only have to check to sqrt(N), not N/2.
Second: You only have to check the primes up to sqrt(N), not every number.
Third: If the original numbers aren't really prime (say they are only good prime canditates), you don't even have to check all the primes up to sqrt(N).

While this may still be a lot of numbers, it's no N/2.

Re:you need a completely *random* key (2)

Anonymous Coward | more than 14 years ago | (#1733624)

If you are using /dev/random as a source of "true" randomness,I encourage you to look elsewhere. I wrote a program to give me passwords from /dev/random once (/dev/random %95)+32 type deal. I started to notice that certain characters were not produced as often as others. I then did many "cat /dev/random >>/tmp/randfile", then I did an 8 bit histogram on the resulting data (I collected 300K of /dev/random), I found some *disturbing* results... like for example the standard deviation was .1, and the extreams in the histogram where > 400 standard deviations away from the mean. in fact I could reliably sort the data on its histogram count. this is not good randomness for a OTP situation.

Large key pools... (0)

Anonymous Coward | more than 14 years ago | (#1733625)

In order to be safe, your key pool would have to be of significant size, at least several billion (1e9) and better, several quadrillion (1e15) keys. Given that your keys have to be at least as long as the message (say, 100k to be sure), the data storage requirements for a large enough key pool are astronomical (100TB in the best case, 10,000ExB in better case). Totally impractical.

You could shorten this by having the keys be only 1kB each, and randomly chosing multiple different keys to fit your message length, but this still would require a public key repository of at least 1TB.

In either case, you still have to distribute the list of which keys to use. While the amount of data distributed is much less (you only have to pass the key numbers, not the data), it still doesn't solve the problem of key distribution, which is the weak link in one-time pads, anyway.

Like I said earlier, and other posters have pointed out, onetime pads are useless for modern computer crypto. They're only useful for top-secret diplomatic use, where the key distro and storage problems are managable.

Remember, it's not just about how strong the algorithm is, it's how strong the protocol is, and if it's practical.

-Erik
(at work, without my cookie...)

Re:Their math is wrong. (1)

Nathaniel (2984) | more than 14 years ago | (#1733626)

While this may still be a lot of numbers, it's no N/2.

in fact, it's less than
1.22506 * sqrt(N) / ln (sqrt(N))

Exactly once, never twice! (0)

Anonymous Coward | more than 14 years ago | (#1733627)

Your comment that if you use it more than once or twice it's easily breakable is quite wrong. Using more than EXACTLY once makes it quite breakable. That's why it's called a ONE TIME PAD.

Re:MAE LING MAK and a modern world view (0)

Anonymous Coward | more than 14 years ago | (#1733628)

Hehe, nice troll.

But you must not have seen the excellent pictures of Mae Ling Mak getting down & funky at Expo Linux World or Linux World Expo or Linux Expo World or World Linux Expo, or Expo: World Linux, or SOMETHING like that.

Woo yeah, she can BOOGIE.

Makes me want to ask her to remove her clothing and then turn her to stone.

Of course, the problem with this is... (2)

Sun Tzu (41522) | more than 14 years ago | (#1733633)

...that to encrypt your hard drive, for example, you would need to retain a decryption key of exactly the same size as the encrypted chunk! While this may be useful for securely encrypting small, highly sensitive files, bulk encryption presents the rather massive problem of managing the key -- which is now as sensitive as the data encrypted.

Re:First? (0)

Anonymous Coward | more than 14 years ago | (#1733634)

I love you, man :P

Seems useless (1)

um... Lucas (13147) | more than 14 years ago | (#1733639)

How are you supposed to exchange pads with the people you communicate with?

Use PGP to encrypt the random data for your one time pad? According to them, all one would need to do is crack the PGP encryped data to retrieve your padding material. If they couldn't break the PGP... then why are you using this? If they can break the PGP... then they have access to your padding info, and can decrypt all the rest of your communications.

I guess you could send email to everyone and have them send their snailmail addresses so you could send them a custom burned CD... but then, someone who was monitoring your email would know this and therefore intercept the CD's, make copies for themselves and then forward them along to their intended recipients...

I just can't see how this is feasible, unless you use public-key crypto to exchange pad or keys...

Why people don't use one time pads (2)

raph (3148) | more than 14 years ago | (#1733641)

Looks like the one time pad strikes again!

Yes, OTP's are completely invulnerable when used correctly. This is similar to saying Micros~1 software doesn't crash when it doesn't come across any bugs.

The essence of OTP is almost trivially simple: generate a large random file, distribute it securely to the receiver of the file, then XOR it with the message. The receiver XOR's it back, and voila, the message!

Of course, the trick here is securely conveying the random file to your communications partner. This is almost as hard as getting a secret message across. You can't email it, or even send it encrypted, because that reduces the security to the weakest link. Thus, all OTP gives you is a form of time-arbitrage. If you can do a secure transmission at time A, that gives you a free secure transmission at later time B.

Then you have to worry about only using the pad once. If you use it twice, your message is totally toast. During WWII, a lot of traffic was gathered this way.

Finally, you need to worry about the keying material. If it's recovered (on either side), your messages are also toast. Since you need to store the key between the time of key exchange and the time of message exchange, it's a pretty ripe target for somebody to snatch off your hard drive. And forget about storing it encrypted - the same weakest link problem.

So this is why people don't use OTP's. You get perfect theoretical security, but in practice keeping track of the keying material is a bitch.

Finally, if you really want to do OTP, I recommend grabbing some /dev/random output and using a simple script to XOR. /dev/random is carefully designed (largely by our own Ted Ts'o). Given what the HardEncrypt people say about sound header files, I find it difficult to believe that anywhere near the same care went into the design.

Happy ciphering!

Huh? (2)

rde (17364) | more than 14 years ago | (#1733643)

For about ten years now, I've been viewing the terms 'PGP' and 'uncrackable' as pretty interchangable. Granted, I'm not the cypherpunk I should be, but I'm pretty sure the only way you're getting into PGP is by some sort of distributed cracking attempt.
Or am I wrong? There's a first time for everything.

Re:Not a very accurate exp. of Prime factorization (0)

Anonymous Coward | more than 14 years ago | (#1733644)

Actually the number of prime numbers is known...

from the Prime number theorem
lim (n->INF) prime(n)/(n * ln n) = 1
at N = 10^9
prime(N) = 50,847,479 and n * ln n = 48,254,942
source pg 837 of Introduction to Algorithms by Thomas H Cormen, Charles E Leiserson and Ronald L Rivest.
Of course this also means that the number of numbers you need to test to find a prime is 1/ln n which is why you can find 2 very large prime numbers fairly rapidly. (Can cut in half if you dont guess evens). This means you can find a 256 bit prime number by guessing approximately 128 prime numbers

And to make a long story short the number of primes between 2 and sq(N) is approximately
n^.5 * ln (n^.5)

A note on OTP key generation (1)

TheDullBlade (28998) | more than 14 years ago | (#1733645)

People have a lot of trouble with the definition of "random number". The key to OTP being unbreakable is that the numbers be unpredictable and well-distributed, with no predictable statistical trends (hmm, I suppose that's an okay definition of random).

There are two basic acceptable ways to get gigabytes of useable OTP key: use theoretically sound true random numbers (the better way), or use a totally personal source of more-or-less random numbers (more or less a type of security through obscurity, with the same major pitfalls that you might screw it up or others who worked on it might betray you).

The first and best method is better covered by more knowledgable people. I'm not entirely sure it exists. There is a theory for generating psuedo-randoms, but that's totally different. The only way to really follow this may be to have a hardware device that generates quantum mechanical noise.

The important thing in using the second method is not to follow any sort of standard method. Pick a random mpeg file, use the numbers as keys in a pseudo-random generator (one key to one pseudo-random; yes, it's predictable and reversible, but most manipulations will be, the important thing is that the data they work on won't be), then use those numbers as offsets to pick out bytes of pi. Roll dice to choose a number to xor an audio file by, then take counts of occurances of each byte value and then partially normalize them to a dice-determined extent by pseudo-randomly (with a dice-generated key) changing the common ones to rare ones. Actually, don't do those things, because if they seem obvious others are probably doing it too. Change approaches each time you decide to whip up a new batch of key. The important thing here is that your approach is original and not standard, so the people who try to make educated guesses based on statistical trends won't have any statistical trends to work from. If they don't _know_ that there are statistical trends, they can't just assume it and get something useful. Of course, these assertions are unprovable; but, IMHO, that a sequence of numbers is truly random is never proven, merely plausible.

Re:Why people don't use one time pads (5)

plambert (16507) | more than 14 years ago | (#1733646)

"this is the first message"
"now here is the second string"

(i guessed at the last part, since they were of unequal length).

it took me about 15 minutes to hack together some perl code to help me do it--easier than doing it by hand.

and i've never done this before. ;-)

it's amazingly simple, actually. you have two plaintexts, T1 and T2, a key, K, and two ciphertexts, C1 and C2. you're trying to find T1 and T2. you don't know (and don't really care about) K, and you know C1 and C2.

so you have:

C1= T1 XOR K
C2= T2 XOR K

now the problem is, we don't know K. so we think about things briefly and suddenly realize:

C1 XOR C2 = T1 XOR T2

which takes the key entirely out of things, making it simply a case of finding two plaintexts XORed together. which is a piece of cake (especially for simple plaintexts like what you provided).

specifically, i took C1 XOR C2 (call it R) and went through it sequentially, XORing the string ' the ' (with the spaces).

this gave me two hits:
07.......e is
11........... firs

figuring it was likely that this string occurred in both T1 and T2, and unlikely that it occurred twice in any one string in such close proximity, i figured these were each parts of T1 and T2, respectively.

then i XORed ' first ' with R in the right spot, and it gave me ' the se'. i tried all the letters a-z after the 'se' which formed part of a word, i.e. not 'sez' or 'sek' or 'sej'.

with some experimentation, part of the message became clear, and it was easy to extrapolate to get the rest.

with some effort, a program could be written to throw a dictionary at it (in nearly any language, and any character encoding or file format) and see what develops. pretty straightforward stuff.

does that answer your question? ;-)

--plambert

Re:What One Time Pads are good for (0)

Anonymous Coward | more than 14 years ago | (#1733647)

Well, a couple of problems:

  • 1.44MB is not alot of keyspace. you can't even send a typical Word document in that space. :-)
  • You can't reuse keyspace. Given that 1.44MB isn't alot to begin with, repeating chunks of the keyspace in subsequent messages is really bad.
  • There is no guarrantee that your seek n random bytes won't choose the same value at least once per month. If it does, well, Oops! Crypto broken!

    Lastly, key management becomes a O(n) problem (assuming all parties use the same disk to crypt/decrypt messages. This uses the 1.44MB even faster. Better, would be to use a single disk for each individual you communicate with, in which case key management is O(n^2). Nasty!

    OTPs are just not any good for general use. Period.

    -Erik
    (At work, without my cookie...)

If you have not, read the page... (0)

Anonymous Coward | more than 14 years ago | (#1733648)

Check out the site if you did not. It explains alot about RSA (and thus RSAREF) encryption types. In essence it said that PGP is secure with todays hardware, but a formula exists for determining private keys based upon host keys, unfortunately it would take a 500mhz machine 10^22 years to crack a single one.

They did, however, allude that the NCSA may have mystery algorithms and supercomputers working on the problem and may have even found a faster algorithm for to do prime factorization, but would probably never release the answer as it would make all their encryption worthless.

If you're the realistic type - pgp/ssh is safe and secure for some time.

If you're the suspicious type - the NCSA can easily crack pgp keys and has been monitoring your box for months.

I am really ffatTony, but that darn passwd escapes me again.

Re:Hard Cryptography & distribution (1)

gas (2801) | more than 14 years ago | (#1733650)

Of course everyone in the world who wants to use strong crypto can. But big USAian things like Netscape and M$ can't integrate it in their programs. So people don't use crypto, it's too hard. (With the exception of "drug dealers", "terrorists" and /.ers of course.)

Re:Why people don't use one time pads (2)

sjames (1099) | more than 14 years ago | (#1733651)

The problem with re-use is that it provides the cracker with a way to verify a guess.

The big problem with cracking a OTP is that there exist many possable keys. Each key will produce a plaintext. The cracker can eliminate nonsense plaintexts, but each sensible plaintext is just as likely as any other. That is, "We attack at 0100" and "We attack at 2153" and "Let's all go home" are all equally likely. If there is a second text known to be encrypted with the same key, only one of the three test keys above will be likely to result in a sensible plaintext for the other message. In short, the solution space shrinks dramatically with each additional use, and the certainty for the cracker increases.

Note, the above example is over simplified. In fact, there are many more possable solutions, and even with two uses, there could still be several possable keys. However, the general ideas are all there.

Re:The Value of OTP(Little/none) (1)

grossdog (15657) | more than 14 years ago | (#1733652)

Other reversible encryption schemes merely make it hard to decrypt a message.


Hard? I think the word you mean to use is intractable, which is to say possible but unlikely in a short amount of time. For example, while it is possible to crack an RSA encrypted message, it is unlikely that it could be done without a tremendous amount of time + resources (assuming a large key).


Also, your thoughts on security "even if your computers were seized" is wrong. If you or your recipient had that block of "random data" on their computer (or cd or whatever), it would be not too intensive to crack the encrypted messages still stored on either computer. OTP encryption is nearly useless as far as digital data is concerned.


It's unlikely that the feds have "cracked" PGP (which is really just a key protocal. It might be more accurate to say either/or RSA Diffie-Hellman). To do so would require either very unlikely mathematical advances (easy to factor large numbers, solve knapsack/travelling-salesman problem, etc) or absolutely ridiculous amounts of computer equipment (1000X distributed.net in a basement somewhere). In other words, pretty unlikely.


This is what happens when people confuse mathematic/scientific terms for their normal English usages. Unlikely really does mean not very likely, but in the sense of intractable rather than "probably not."


--Andrew Grossman
grossdog@dartmouth.edu

Slashdot articles are bull.. (0)

Anonymous Coward | more than 14 years ago | (#1733653)

I know this is highly off topic, but I have no other way to get posted I think. I think you all agree that this article is totally pointless. Just another lame encryption software. Slashdot has more and more of such stupid articles like Katz's articles,or Yet another article why (Linux/Gnome/X/free software/open source) is better or articles about movies nobody cares about or Yet another stupid crypto scheme. My problem is that I already posted half a dozen articles that were IHMO more important than half of the articles on slashodts. Eg: - Article on the first FULL FEATURED linux game that had to be cancelled due to money problems. - Something about a company saying a software is open source and free during dev, abusing testers and then closing source and asking money. - Links to the recent MAJOR busts in the warez scene on groups like Razor1911, Hybrid, Fairlight, Paradigm, Origin (NY Times, yahoo,ZD) They didn't publish that on /., but 3 days later they published an article about a kid beeing convicted for warez. I don't remember for the others. So, I know that /. has really a lot of submission everyday. But are my submissions totally irrelevant or is there some segreation?

Re:The Value of OTP (0)

Anonymous Coward | more than 14 years ago | (#1733664)

Perhaps. However, you should most certainly NOT keep your keys on permanent media like CD-R. You should be destroying the keys as you send messages. Otherwise, all the opponent has to do is get ahold of your key media, and that's all she wrote...

The key distribution channel is of course the weak link. How can you be sure that someone didn't intercept the key holding media? What about breaking in, and copying the media before the message is sent? At least using PGP and other RSA implimentations, your private key is passphrase protected, and you generate session keys at the instant they're being used.

Also, as I've pointed out elsewhere, OTB is completely impractical for comunnicating with multiple people. It's strickly one-to-one. So, you have an O(n) key distribution problem for a typical group of people. This sucks hard.

OTPs are not useful in general computing. Period. Any attempt to pretend that they are is foolish, and gives a false sense of security.

-Erik
(At work, without my cookie...)

Re:Got one thing right. (0)

Anonymous Coward | more than 14 years ago | (#1733665)

Their code may not recycle the key, but their documentation on the website recommends reusing the key file for convenience!

The same with BR tags (0)

Anonymous Coward | more than 14 years ago | (#1733666)

I know this is highly off topic, but I have no other way to get posted I think.

I think you all agree that this article is totally pointless. Just another lame encryption software. Slashdot has more and more of such stupid articles like Katz's articles,or Yet another article why (Linux/Gnome/X/free software/open source) is better or articles about movies nobody cares about or Yet another stupid crypto scheme.

My problem is that I already posted half a dozen articles that were IHMO more important than half of the articles on slashdot.

Eg:

- Article on the first FULL FEATURED linux game that had to be cancelled due to money problems.

- Something about a company saying a software is open source and free during dev, abusing testers and then closing source and asking money.

- Links to the recent MAJOR busts in the warez scene on groups like Razor1911, Hybrid, Fairlight, Paradigm, Origin (NY Times, yahoo,ZD) They didn't publish that on /., but 3 days later they published an article about a kid beeing convicted for warez.

I don't remember for the others.

So, I know that /. has really a lot of submission everyday. But are my submissions totally irrelevant or is there some segreation?

So drop the header (1)

tilly (7530) | more than 14 years ago | (#1733667)

I said sample it, not use the whole thing. Chop off the header and what is left is a good simulation of random data. In fact to the extent that it is *not* a good simulation of random data, it is further compressible...

Cheers,
Ben

Re:As I Understand It (1)

cananian (73735) | more than 14 years ago | (#1733668)

Let me see if I can improve your explanation.

PGP and friends do rely on hard mathematical problems. Factoring large numbers is a problem that has been studied for hundred of years. Algorithm improvements *have* taken place. Factoring a 512-bit number used to be unthinkable; now it is (just barely) possible. 4096-bit numbers are many many orders of magnitude more difficult. So it is possible to extrapolate from the current rate of algorithm improvement and an estimate on how far ahead of "the rest of us" the NSA is to get an idea of how secure PGP is. Give the NSA ten years advance, and 4096 bit keys are still safe for a couple of decades (at least!).

And, no, it is *extremely* unlikely the NSA would *ever* be able to factor 4096-bit numbers in *seconds*. Admittedly no one's been able to prove a lower time bound on the integer factorization method, but this problem *has* been studied for centuries. Quantum computing *could* change the paradigm, but the amount of precision one needs for 4096 bits is quite daunting.

And the "near primes" that PGP uses have an astronomically small chance of being non-prime. Basically, the parameters of the algorithm are chosen so that it's about as likely that a person can randomly guess the symmetric key. And generally if the number is non-prime, PGP encryption just plain won't work. Which means that *no one* is able to decrypt your messages (not even you) --- a situation that would be quite obvious if by some miracle it occurred.

Please read
http://www-users.informatik.rwth-aachen.de/~send erek/certify/secret-key.protection.html
for more information.

NSA *has* broken OTP before (1)

Nelson (1275) | more than 14 years ago | (#1733669)

The Verona documents cover it.


OTP is provably secure, if used properly. Use a pad twice and it's not just insecure, but it's almost completely insecure.. Conventional block ciphers and stream ciphers suffer from weaknesses but they are usually only partial weaknesses.


If you've got important data, a good source of random bits, and the discipline to use it, OTP is unbeatable. For most of us something like PGP is plenty, (or GPG, when are they going to plug RSA in? on my birthday next year?)


In some circles, the belief is that the outside world has caught up with NSA technology, I've heard more than one well known cryptographer make that statement, it's really just an issue of funding. NSA can build bigger and faster computers but there is a level where that doesn't add up to much. RSA (800+bit) and 3DES are most likely secure beyond your lifetime..

Re:Why people don't use one time pads (0)

Anonymous Coward | more than 14 years ago | (#1733670)

I see. That's a cool idea. Thanks. Alex.

I'm not sure that's right (1)

ffatTony (63354) | more than 14 years ago | (#1733671)

After an initial secure communication of random bytes, you can send the same amount of data over insecure communication routes in absolutely perfect security.

I don't think thats correct. As I understand OTP if you re-use the key the complete security is broken. As the randomness is gome. In order to use an OTP and securely communicate with a friend you must exchange a new key before each transmission. Thus the steps would be more like

  1. make key (Which is the same size as the data)
  2. exchange key in some secure way
  3. exchange encrypted data securely
  4. Goto 1

Nobody could ever crack it, no matter how many billions of dollars worth of computer equipment, no matter how much computers improve, no matter how many millenia they spend on it.

Nope. no one could crack the first one, but after that it would be possible with a difficulty depending upon how the data and key were combined.

Re:Huh? (2)

scrytch (9198) | more than 14 years ago | (#1733672)

PGP is not "uncrackable", merely "hard". A OTP isn't a mathematical problem, it's a pre-established secure channel. The trick of course is in establishing that channel. And you can't reuse it.

Why? (1)

Vryl (31994) | more than 14 years ago | (#1733673)

I don't actually believe it for a second. I think we have gone further than the TLA's (see my Everything node [http] on TLA's).

There are more of us, we have less obstructions in the way we communicate (why work for the military when everything you do is watched and your every movement under suspicion, and who you are allowed to converse with strictly limited), and our stucture (or lack of) allows ideas to propagate faster.

We have outpaced the poor fools in the NSA and others and will overtake them soon, if we have not already done so. Things like 'milspec' slow down their processes enormously and they are losing their edge. And yeah, they are shit scared. Witness all the legislation attempting to censor the net and more.

PGP and other public key systems are very secure. The factorisation problem has not been solved. Shortcuts may have been found, but increased key lengths will easily keep up with this.

-- Reverend Vryl

I disagree (1)

ffatTony (63354) | more than 14 years ago | (#1733680)

I care about movies and The Who, but I think some Floyd plugs would have been nice (R. Waters is on tour right now.).

I did not think that this article was that bad. The code needs some revision and more planning, but OTP is a encryption possibility. It seems good to have as many options as possible.

I don't understand why you'd visit a site if you did not care for the subject matter.

Has anyone else noticed that slashdot's banner adds appear a good thirty seconds to a minute before the page appears on win32-ie5 and linux-potato-netscape-461? A conspiracy? I think yes.

node (1)

Vryl (31994) | more than 14 years ago | (#1733681)

here [blockstackers.com]

yeah, yeah . . . preview before submit . . .
It ain't that exciting a link anyway.

-- Reverend Vryl

Zooko says: DO NOT USE THIS PROGRAM (0)

Anonymous Coward | more than 14 years ago | (#1733682)

Zooko here.

Please please don't use this program for anything important. It is NOT a true one time pad. I just had a quick look at the source code, and it is generating the pads by scrambling an input file using "rand()". (And as far as I noticed it doesn't even mix each individual 8-bit byte at all.) It is pathetically insecure. Even _I_ could probably crack your messages if you used this program.

Roblimo deserves a slap on the wrist for wasting all of our time with the 10000th bogus "one time pad" program ever invented.

I trust PGP for all of my encryption needs. I also trust ssh and hushmail.com. If you don't choose to do that (i.e. you really don't want to take the risk that some enemy of yours might have a new factoring algorithm or a quantum computer), then you can roll your own true one time pad using /dev/random. But if you do that, you'll have to be very careful about the details. Most likely you'll screw up and get zero security when you're done. Maybe we need a "Real One Time Pads HOWTO"...

Zooko [who doesn't have access to his slashdot account right now]

Re:Some thoughts on encryption (1)

Detritus (11846) | more than 14 years ago | (#1733683)

You can get a geiger counter with a PC interface for $150 at Aware Electronics [aw-el.com]. A radiation source can be obtained by disassembling a $10 ionization smoke detector.

With a little bit of software, you have genuine random numbers.

I don't think OTPs are as impractical as some people say. I can put 1.44 MB of random numbers on a floppy disk and hand deliver it or send it via registered mail to my correspondent. That will encrypt a lot of email. The U.S. Government routinely uses registered mail for classified documents and keying material.

Re:As I Understand It (1)

mbyte (65875) | more than 14 years ago | (#1733684)

The problem is, that it is not known how "hard" factorisation is. I.e. there is a small,but existing chance, that there is some algorithm that solves factiorisation in polinomioal time.

So : Factorisation element NP = ?

Re:Some thoughts on encryption (1)

Madwand (79821) | more than 14 years ago | (#1733685)

There is one industry (and its regulators) that must deal with RNGs on a nearly daily basis: the Gambling (excuse me, "gaming") Industry. The question is, what sort of hardware or software RNGs do they use, and how do the various regulators (e.g. the Electronic Services Division of the Nevada State Gaming Board [state.nv.us]) verify that the RNGs are random enough?

Re:Not a very accurate exp. of Prime factorization (0)

Anonymous Coward | more than 14 years ago | (#1733686)

Duh. You're right. I apologize for the misinfo. Bart

when calling cards were king (0)

Anonymous Coward | more than 14 years ago | (#1733687)

id have to agree id certainly find this kind of stuff interesting. Anyone know what happened to Maxamillion after he got put in jail for CC fraud? Hey Fiona we going to the beach any time soon?:) Tempest the best BBS software ever.

Re:This is NOT a troll (0)

Anonymous Coward | more than 14 years ago | (#1733688)

Couldn't this qualify as informative?

Re:The Value of OTP (1)

TheDullBlade (28998) | more than 14 years ago | (#1733689)

"you should be destroying the keys as you send messages" I agree, if you are worried about someone seizing the storage media. A basic assumption of OTP is that the keys are being stored securely and used on a secure machine. Anyway a CD-RW would be just as easy to send, if a little more expensive.

OTPs are perfectly fine for long-term, low-bandwidth communication, and you don't have to worry about some new magic black box (like a quantum computer) coming along five years down the road and having all your old messages that someone stored instantly open, or ever having to update your encryption software (your keys, OTOH...).

Imagine having a smart bank card that stored enough OTP key for a year's worth of transactions. Once a year (or time unit X), you'd have to feed it into your presumably secure local branch computer, which wouldn't be too inconvenient. It could be the only long-term (as in credits for the Galactic Republic, though it might become necessary much sooner) solution for verifiable money.

Also, OTP is not "strictly one-to-one," it is like any other symmetric reversible encryption (except, as I said, that the keys are large and are consumed on use, and it is unbreakable). It can be "group-member-to-group", where everyone with the key data can send and receive messages to everyone else. I suppose I'm splitting hairs here.

BTW, I never said it was a good general replacement for public-key encryption, or securing your data in an insecure storage location.

>"OTPs are not useful in general computing. Period. Any attempt to pretend that they are is foolish, and gives a false sense of security."

I don't know how to argue this one, since "general computing" is too fuzzy a term to argue with. One could well argue that encryption in general or 3d cards have no use in "general computing." I agree it's excessively troublesome for the typical user who doesn't care if the FBI or a rival corporation is listening, or if it might be cracked in a few years. I certainly don't see how, when correctly used, it could give anyone a false sense of security, unlike encryption schemes that can be broken by sufficiently motivated groups.

Re:Snake Oil (1)

psaltes (9811) | more than 14 years ago | (#1733690)

You must not have looked very closely...in a OTP the randomness comes from the pad, not from anything in the program. Their documentation explains why rand is useless for encryption. The source file GenKeyFile.cpp (which may use it, i dont know) is intended for use by "casual users", ie those too lazy to create some sort of truly random pad, according to their docs.

Zooko says: hushmail rocks (0)

Anonymous Coward | more than 14 years ago | (#1733691)

Zooko here.

hushmail does end-to-end encryption. A Java applet does all the encrypting/decrypting on the end-user's computer, so neither the hushmail.com computers nor anybody else can get the plaintext.

It's a great idea, and I trust the people who are connected to it (systemics.com, cryptix.org, cypherpunks.ai, e-gold.com), but I have to admit that I haven't looked at the hushmail source code yet.

Reusing OTP's (1)

DiningPhilosopher (17036) | more than 14 years ago | (#1733692)

Well, you can "reuse" an OTP in a sense - if you have more pad data than you need you can save the rest for the next operation. You just can't reuse the same sequence.

For example, as another poster suggested you could share a really huge random stream on DVD between two locations. Then as long as you store some indication of the last byte used you can use up the data in small chunks, and when you run out you get a new DVD.

All you'd need would be a wrapper program which called HardEn/Decrypt with the message and an appropriately sized chunk of data from the DVD. This program would keep a record of the current position on the DVD, but the DVD would still hold the keying material and you couldn't do anything without it.

You misread it (1)

TheDullBlade (28998) | more than 14 years ago | (#1733693)

The thing about OTP keys, is that they don't come in fixed sizes. The key's size for a message is equal to the message size. So you just initially transfer as much key data as you want and then use what you need as you need it.

So if you share a few gigabytes of random data with a friend, everytime you want to send a message, you chop out an appropriate quantity of noise, use that as the key and never use it again. Of course, you'd have to take care that you and your friend were using the same piece of data for the same message, but that's trivial (prefix to the message the offset into the data table you gave, or something similar).

Indeed, though, they are called One Time Pads for a reason. If you reuse a key, or part of a key, the key (or part) can be cracked.

The point that many people seem to be missing is that you can transfer key data for an arbitrary amount of communication at one time. You don't have to be constantly couriering keys for each individual message. You don't need the message to make the key.

Re:Not a storage encryption method. (2)

Sun Tzu (41522) | more than 14 years ago | (#1733694)

In that case the key management problem is even worse, don't you think? That old annoying secure channel paradox: You need a totally secure channel to exchange the key. However, if you have a totally trusted secure channel you don't need encryption at all.

The exception, of course, is if you have a secure channel at one point in time for key distribution and to establish a protocol for exchange of data at a later time... just don't run out of OTP key data! And, of course, now both the originator and the recipient of the data must securely store the OTP data ... it certainly will be too long and random to memorize. I'm afraid OTP's are even less useful for secret data exchange than storage encryption.

Re:pgp not secure (0)

Anonymous Coward | more than 14 years ago | (#1733695)

source is available.. show me the backdoor !

Re:pgp not secure (1)

simm_s (11519) | more than 14 years ago | (#1733696)

Do you have any proof? Any articles to validate your point. Did they back door commercial PGP or PGPI?

I doubt they have better algorithms (1)

tilly (7530) | more than 14 years ago | (#1733701)

To the best of my knowledge, more intellectual energy is being thrown at the problem of factoring in the mathematical community than the NSA and friends can probably muster. For that reason I doubt that they can get, let alone maintain, a significant lead for very long on the theoretical side.

However on the practical side using routine application of current theory and sufficient money (ie hardware) you can indeed get better results than are publically available. It is a safe bet that various 3 letter agencies have made this investment and can crank through tremendous volumes of material encrypted with legally exportable encryption.

Incidentally anyone with any questions on encryption should wander over to the RSA [rsa.com] folks.

Cheers,
Ben

Completely secure communications is useless????? (0)

Anonymous Coward | more than 14 years ago | (#1733702)

This is not public key encryption. If you need to communicate with people who you have never met in a secure fasion then you need public key encryption.
But if you want to communicate in the only proven secure way then you need OTP. It's what they use to launch nukes by the way. Yes it's a bitch that you have to actually meet the person and hand them the key. Just get a CD's worth of random data and burn two copies. Keep one and bring one to your secret lover and now you can send a CD's worth of email that not even God can read. Well unless he gets a copy of your key.
This gives you completely secure email capability and now all you have to worry about is physical security of your key and tempest but you are way way ahead of where the NSA would like you to be.

Re:Zooko says: DO NOT USE THIS PROGRAM (1)

Tom Rothamel (16) | more than 14 years ago | (#1733703)

I trust PGP for all of my encryption needs. I also trust ssh and hushmail.com.

While I trust PGP and SSH, at least for versions in which I can get my hands on the source, I'm interested in knowing why you trust hushmail. It just seems to me that directing mail through a central server is a good way to blow security. Even if hushmail is secure and honest (and I have no reason at this time to doubt either), it just seems to me that this is adding a weak link to the chain that really doesn't need to be there.

Did their homework? (1)

Compuser (14899) | more than 14 years ago | (#1733704)

Quote:
"given a large number N, if you know that N has two factors, you can
find them by trying to divide N by every number up to N/2".
Apparently no math major has reviewed their work (should be "up to [sqrt(N)]",
where [] denotes integer floor function).

No they havn't broken it. (0)

Anonymous Coward | more than 14 years ago | (#1733705)

Not even God can break it. They recovered the plaintext because whoever generated the key didn't know what they were doing or used it more than once.

Re:Why people don't use one time pads (1)

EJB (9167) | more than 14 years ago | (#1733707)

I knew the theory, but I'd never seen it in practice. Pretty cool. I guess all the moderators ran out of points so I'll just add a reply, since this is about the most relevant message for this article.

EJB

Re:The Value of OTP(Little/none) (1)

TheDullBlade (28998) | more than 14 years ago | (#1733708)

Hard? I think the word you mean to use is intractable, which is to say possible but unlikely in a short amount of time. For example, while it is possible to crack an RSA encrypted message, it is unlikely that it could be done without a tremendous amount of time + resources (assuming a large key).

A short amount of time is a very fuzzy concept. "Intractable problems" from a few years ago are being solved today. Who knows what'll happen in the coming years? Proven mathematical impossibility can be very comforting in the face of unpredictable future developments.

I agree with the idea that some other encryption schemes are good enough, so long as nobody cares about your encrypted data enough to want to hang on to it to decode it even if they can't manage it for years.

Also, your thoughts on security "even if your computers were seized" is wrong. If you or your recipient had that block of "random data" on their computer (or cd or whatever), it would be not too intensive to crack the encrypted messages still stored on either computer. OTP encryption is nearly useless as far as digital data is concerned.

Kindly note that I qualified this statement with "If you both deleted the used key data after communicating, and he deleted the message after reading it". In the case I was referring to, there wouldn't be any "still stored" messages or key data you are talking about them using. Of course, you would have to take inconvenient precautions to prevent this from happening. The exceptional situation you are referring to is analogous to someone bursting into the room while you are editing a message; it is also solvable by similar means: only take messages at pre-arranged times, have your system configured to auto-delete when you aren't there to receive, and have your system configured with a panic-button or deadman switch which you man while receiving to auto-delete if you are interfered with. The alternative is special hardware rigged with self-destruct mechanisms. Of course, now we are talking about some ridiculous extreme spy-vs-spy security; most sane people would be happy with an auto-decode and cleanup on reception and encryption in a less secure fashion for those messages which are being temporarily stored before being read (actually most sane people are happy without encrypting their email...). The point I was making is that once you're done with a message and you've cleaned up after yourself, it's utterly gone, no matter who has recorded the insecure transmission or what they're willing to spend on decoding it.

Re:Looks OK, but the problem with 1-time pads is.. (1)

Zigurd (3528) | more than 14 years ago | (#1733710)

1. True, but...

2. Yup, you gotta carry the DVD ROM disk to the other endpoint and you gotta have some way to know the other endpoint hasn't been coerced or turned. A problem for spies, but OK for most commercial use. It also gets unwieldy for large groups, especially if the same info has to be securely transmitted to many people. Too hard to keep track of that many key disks. But if your object is to connect two people securely, it's no biggie.

3. A DVD ROM is about 6GB, full rate speech on the telephone network is 64Kbps or: 8KBs, 480KB/min (roughly half a meg, let's say), so that's 30MB/hour, and over 30 hours of speech encoded with one DVD's worth of OTP key. Compress the speech 8:1, and you get 240 hours per disk! You talk that much and people might begin to suspect a conspiracy.

Weigh the problems against the benefits: it's so simple, real time speech encoding and decoding is no problem at all, even for multiple channels. This is where high key length public key falls down: it is too computationally expensive for multi-channel real-time voice. The required hardware is so simple that you can go to great lengths to assure yourself there are no exploitable features in the hardware. Use a DVD RAM and your hardware can be programmed to erase the disk as it is used up to idiot-proof the system. And the code is so small it can be trivially exported in printed form.

Author doesn't know beans about one time crypto (2)

A nonymous Coward (7548) | more than 14 years ago | (#1733713)

The very name tells you the one time pad is meant to be used one time, yet the author states:

After you make a key file, you can use it over and over again

and helpfully suggests that

you might want to make a separate key file for each person with whom you want to exchange encrypted files

No no no! You DO NOT re-use one time pads. You DO NOT share one key with multiple people even with "lesser" crypto systems, but ESPECIALLY withone time pads, because that implies re-use.

One time pads are only unbreakable when used just once. Multiple uses leave clues for analysis.

Anyone who knows even a little about crypto knows that the weakest link is managing the keys. That's why PGP's private keys are hidden by that obnoxious pass phrase. If the black bag guys break into your computer and copy your PGP files, they still have to decrypt them because your pass phrase muddles things. With this one time pad, they have the key immediately, no further work required.

This guy seems to imply you should keep your one time key lying aorund the hard disk so you can encrypt and decrypt at will. Good gosh, PGP encrypts the private key with the pass phrase at least. Here you leave your one time key OUT IN THE OPEN, and REUSE it, over and over again. This is NOT secure crypto.

THIS IS LESS SECURE THAN PGP. This is a silly little toy and DOES NOT PROVIDE SECURITY.

He massively understates how easy it is to factor RSA private keys. He says "it is possible", yet he is wrong. Until and unless new algorithms are found, there are not enough atoms in the universe to factor 4096 bit keys before the universe collapses back into the next big bang. Luck does not enter into it. There is only so much theoretical computational power available in the lifetime of the universe; it won't crack even a single key. And if you spread it over multiple keys, then the chances for any single attack drop correspondingly.

--

Got one thing right. (1)

ry4an (1568) | more than 14 years ago | (#1733720)

I was really afraid I would see them recycling the key if it wasn't long enough. Fortunately this code snippet shows they at least got that right:

if(numKeyBytesRead < numInBytesRead) { // check for a small key
printf("\nERROR: keyfile must be at least as large as input file.\n");
printf("Output file is incomplete\n");
}

Of course they don't bother with how the sender/receiver should exchange the key file in a secure fashion.

Looks OK, but the problem with 1-time pads is... (2)

trims (10010) | more than 14 years ago | (#1733721)

...that they're almost completely useless for most tasks.

A full discussion of one-time pads can be found in Applied Cryptography, 2nd ed, by Bruce Schneier (page 15).

One time pads have several problems that make them useless for anything but locking individual files (and even then, it's quite a pain).

  1. You can never use the same key for more than a single message.
  2. It's a secret key algorithm, which means that sending the message to someone else requires that you get the key to them somehow. Key distribution protocols are generally extremely difficult to impliment in a secure way (which is why public key crypto is so popular, since it provides a nice solution to the problem).
  3. key storage is a problem. Since you have to store all the keys, and since a key is as long as your message, key management is a pain in the ass. Storing them using a pass phrase reduces the security to the level of your pass phrase, so you might as well use RSA or even DES/blowfish.

Onetime pads, while cool in a theoretical sense, are useless to virtually everyone with the exception of diplomats. For diplomatic use, they can solve the key storage/distribution problem via CDROMs/Digital tapes transport via diplomatic courier bags. Everyone else is screwed. Even the millitary doesn't generally use onetime pads because of the key distribution problem.

Stick to high-keylength public key or symetric cyphers. They're far more useful, and the likelihood of them being broken by even the likes of the NSA is not good.

-Erik

Or just use a one-line perl script and /dev/random (0)

Anonymous Coward | more than 14 years ago | (#1733722)

And the author of the page doesn't seem to make it clear that you can onle use the pad ONCE. Many times he says 'messages' where he certainly needs to say 'message.' If you use the same OTP more than once or twice, it's easily breakable. Also, check out http://www.ilogic.com.au/~dmiller/files/audio-entr opyd-0.0.0.tar.gz if you have a stereo sound card and need more entropy for your /dev/random.

Some thoughts on encryption (2)

tilly (7530) | more than 14 years ago | (#1733723)

The first thing that amazes me is that we don't have a good random number generator in hardware. For various reasons you cannot build a perfect one in software - software has to be deterministic. But you can in hardware.

The trick is that you have to come up with a process that generates a random bit-stream. The classic example is 2 Geiger counters side by side. (Throw away results from both that arrive shortly after the either fires. There is a slight latency and this gets you independence.) There are variations of this that can easily be set up in silicon much more economically.

But, you say, this gives you a biased stream? Yes, but an independent, random one. The next step is to take the output in pairs, drop the pairs that are the same, and then take the first bit. This gives you an independent unbiased bit stream. Well there is a miniscule bias, however it is slight enough that it would not be reliably detectable if the machine operated for several billion years. I consider that acceptable. :-)

This does throw away about 3/4 of the data. Some of this can be recovered and used, after all your "accept, don't accept" is a bit-stream, and so is the set of values from the pairs that agreed. Both are more heavily biased than your original, but a few layers of this will get a lot more information extracted.



Unfortunately no such random number generator done in hardware is widely deployed. If it were then encryption would be a lot better than it is today but...


My other thought was an encryption algorithm that requires lots of random data, but is better than a OTP for transmitting a stream. First of all a common but bad algorithm is to XOR a bit stream with a random block of data, but reuse the block. While a OTP is unbreakable this variation is easy to break. Just XOR the output with itself shifted over, and when you hit the length of the stream you will get a large spike in certain characters. That tells you the length and a good cryptographer can work quickly from there.

A slight variation on this would be to have 2 random blocks of data, of different length, and XOR both of them against the original. This is still breakable but it is harder since each block hides the other.

My idea is to have the 2 random blocks of data, but have the transmitted stream of data be randomly sending the message and replacements for each block. This means that the random blocks of data are each hiding the other and the transmitted changes to the key, while they are themselves getting replaced.

I suspect that if you devote enough of your bitstream to the replacement of the bitstream that this variation is very secure. Unfortunately it needs a large supply of really random bits, and that is not easy to come by...

Regards,
Ben

PS One supply of pretty random data is as follows. Compress some large binaries as much as you can, and then sample the result. A well-compressed file looks a lot like random data...

Re:MAE LING MAK and a modern world view (0)

Anonymous Coward | more than 14 years ago | (#1733724)

I don't know. As far as I know, she hasn't yet. If she were to say something negative about it, well, I'd drop the thing, but I would assume she doesn't have a problem with it. (Sidenote: Am I the only one who's noticed that Segfault seems heavily Slashdoted over the past day or so? I can barely even load the front page right now)

As I Understand It (1)

Vryl (31994) | more than 14 years ago | (#1733725)

The problems with public-key (diffie-hellman, pgp and the rest) lie with 'hard' mathematical problems, such as factorising large numbers and the discrete logarithm problem (with the eliptical curve algorithm there is a similar hard math problem). The bet is that the NSA or others have found a way to factorise large numbers much more easily than is currently known publicly. This would make PGP crackable is something like seconds or minutes, not months, years or millenia . . . As I understand it, PGP is actually based on an algorithm that generates 'near primes'. ie, the numbers are considered prime even if they are not due to the likelyhood of them being prime. Someone more knowledgeable may be able to add more info to this, but I think this is the crux of it.

-- Reverend Vryl

Not a one time pad :-( (1)

Eric Kidd (21408) | more than 14 years ago | (#1733726)

This isn't a one time pad, and it's not terribly secure.

Why This Program Isn't Very Secure

Audio data is not very random. It contains lots of patterns. Record a sound file (or save an MP3 as a WAV) and look at the file. Some bytes show up more frequently than others. So at a minimum, an attacker can probably perform some messy statistics and discover some general things about your file--which byte values show up more often than others, for example.

Some Good Things About This Program

This program uses a poor encryption algorithm but a very large key. So even if parts of the file are decrypted, other parts will always be garbage. Most attacks on this progam will give probabilities, not definite results.

How to Fix It

Remove the one-time-pad entirely. Replace it a quality block cypher (this allows you to use the same key more than once, which you can't ever do with a one-time pad). Use your audio file (or other file) to generate a large key. Decide on a way to use your enormous key effectively.

How to Lean More

Read Applied Cryptography. [counterpane.com] Modern cryptography is very, very good, and there's no reason to fool around with one-time-pads and pseudo-random number generators.

Not uncrackable, but close (1)

drig (5119) | more than 14 years ago | (#1733727)

PGP isn't uncrackable. It's just astronimically hard to crack. On the order of 1000s of years witrh every atom in the universe dedicated to it. But, in theory, it's crackable. Also, if someone comes up with a better way to factor large numbers, PGP is vulnerable. This is true of all modern public key cryptosystems (except maybe for Elliptical Curves which I don't know much about).

Theoretically, a OTP is uncrackable. No amount of computing power can crack, not matter how long you try.

Ok everyone, check this out. (0)

Anonymous Coward | more than 14 years ago | (#1733728)

What I keep hearing is how difficult key management is using OTP. When used correctly, OTP is absolutely and 100% secure. It will be forever and ever. Now you still have to worry about physical security and tempest, but as for data you send through the Internet, you're completely safe. If the message is intercepted and archived, it will never be decrypted without the key. Something that can not be proven with programs such as PGP. Why couldn't a program be written to automate key management? Here's what you could do:

Dedicate a standalone PC, no network connections at all to be your "secure email station." Transfer the encrypted files and files received from the net to be decrypted via floppy between this and your Internet computer. On the secure station, you set aside a huge partition - a gig or ten - (disks are cheap now) to be your pad and ensure it contains totally random noise. Now dd this to a partition of equal size on another physical drive, take that drive out and physically give it to your secret lover.

Now you need a program that will do the following. You encrypt a plaintext file with some blocks from the key partition. Your program would append a list of which blocks have been used to encrypt the cyphertext and then wipe these used blocks from the drive. The reciever would look these blocks up on his or her identical partition and decrypt the love letter before wipeing the used blocks from the face of the earth. One side would the first half for encryption and the other would use second. If you're into three ways (or more) then each of you would split it into three pieces, etc.

Once you have two or more hard drives with identical partitions containing blocks of random noise, take a vacation and bring your secret lover(s) a hard drive. You do physically see your secret lover from time to time don't you? From now on you can send email back and forth to your hearts content. Well 'till you've sent a gigabyte or whatever worth of love letters.

I've thought about doing this with CD's but you can't delete the used blocks. This would not be a problem if you could guarantee physical security on each end, but it would enhance physical security in the sense that you could take the CD out. Another even more physically secure method would be to load a huge ramdisk, run Linux for stability and make sure the computer is on a UPS. Now your secure station would ask an access password and immediately erase the ramdisk if it's wrong. You could even go overboard and put tamper switches on the case that cut power to the ramdisk. Just some thoughts and I would apreciate feedback because I may just write such a OTP key management program if I ever get the time.

More to the point (0)

Anonymous Coward | more than 14 years ago | (#1733729)

What you mean to say is that the "key generator" is insecure. You can generate a secure key with other means, and the program is Open Source, if you know what I mean.

One can always use PGP to encrypt the results of the OTP program :))

The U.N. doesn't care . . . (0)

Anonymous Coward | more than 14 years ago | (#1733730)


I don't care how many bits your key is, 8192 or 65536, you have NO HOPE of security because the U.N. can crack it.

When your new masters from Tel Aviv throw you in the slave-labor camps, don't come crying to the true patriots who died defending their God-given freedom.



Re:Seems useless (0)

Anonymous Coward | more than 14 years ago | (#1733731)

You give _A_ pad to everyonr that MIGHT need this ULTRA high security measure, IN PERSON, before you need it. Then you reserve it's use till you NEED it. Fresh pads are always given out in person

Convinience is the point (1)

simm_s (11519) | more than 14 years ago | (#1733732)

Assuming hard crack is "potentially" incrackable, I don't think it is very useful. Public key crypto like PGP, on the other hand, is more secure for online mail and commerce. It may not be uncrackable but because the encryption keys can be sent publically it is more useful. Hard crack is as secure as the key transport system. I think hard crack is great for my security at home. Where do I hide the key????

Why OTP is proven uncrackable, in laymans terms... (0)

Anonymous Coward | more than 14 years ago | (#1733733)

Theoretically, a OTP is uncrackable. No amount of computing power can crack, not matter how long you try.

It's more than just a theory. It's proven. This is because, for example, a 10 megabyte file (properly) encrypted this way contains, in the absense of the key used to generate it, any message that a file of that size can possibly contain. It contains Shakesphere, in Real Audio format, as read by you in any language, including extinct languages and languages that have never existed, with or without an accent, with or without a cold. It contains every great novel that there has ever been - or will be. It contains your deepest darkest secrets or those of anyone who has ever lived or ever will. It contains the secret of the universe or the answer to who shot Kenedy or what really happened to the TWA-800 flight. It has any of yesterdays newspapers or even tomorrows. It contains the winning lottery numbers for each and every lottery and also every loosing number that will be drawn - or won't be. It contains this entire discussion on OTP, with me First! Including a great big old GIF of my butt! (Or jpeg, etc.)

The point is that you don't know what the message is, and even if you guessed it, you would never know you had the right one. A properly encrypted OTP file contains, (again, in the absense of the key used to encrypt it) each and every message that a file of it's size can represent. This is what makes it unbreakable and it's more than a theory. It's as provable as 2+2=4.

This is NOT a troll (0)

Anonymous Coward | more than 14 years ago | (#1733734)

The post I'm replying to is NOT a troll. It's Offtopic. Get it right!

I will provide an example of "Troll", "Flamebait," and "Offtopic" so that everyone may moderate a bit better in the future.

TROLL (Creating and stating absurd opinions for purposes of pissing people off): "Linux obviously sucks very much, we alll know it's an evil plot by the demon-possessed feminists in the National Organization for Women, who support eating babies and sacrificing children to their dark female gods! If you want to know the REAL TRUTH about the fiends, visit THIS WEB PAGE! Also, BeOS sucks because it's based on Linux, so it's just as evil as Linux. FreeBSD sucks because it's also based on Linux. Microsoft RULES because it's the only Operating System that's not based on Linux."

FLAMEBAIT (Trying to piss people off just in general): "BeOS SUX SUX SUX!! Suck it down, bitches! If you don't like it, SUCK IT, because YOU SUCK, and if you use BeOS you're a DUMB And you're GAY, and you SUCK!"

OFFTOPIC (discussing something other than the subject at hand): "The post I'm replying to is NOT a troll. It's Offtopic. Get it right!

I will provide an example of "Troll", "Flamebate," and "Offtopic" so that everyone may moderate a bit better in the future..."

Now, practice on THIS POST here. NOTE: I've given you a BIG HINT already.

pgp not secure (0)

Anonymous Coward | more than 14 years ago | (#1733736)

The only secure versions of PGP are pre 2.3a every version after this has a back door, the back door was placed because of government demands. if people reply to this ill post the secure version somewhere for dloading.

NSA vs NCSA (1)

DiningPhilosopher (17036) | more than 14 years ago | (#1733738)

I believe you mean NSA... NSA is the National Security Agency, a government division which almost certainly has hardware and software beyond our imagination for cracking that which we consider uncrackable.

NCSA is the National Center for Supercomputing Applications, which theoretically could be dangerous in this regard but in practice doesn't concern itself with such things.

I DO NOT UNDERSTAND *it* j/k (0)

Anonymous Coward | more than 14 years ago | (#1733741)

i dunno if you guys know it but w/ PGP you do have a choice (not only DH/DSS)-guys im sorry but coming from win (first 2 years in the whole linux thing) i could never get used to the command line PGP, on the other hand the v.6x for windose is nice!) and supports RSA 2048 bits. now im personally very paranoid (i know you are watching me!!! hehe j/k) but u know im feeling confident with that kind of security right now. Yes the pgp packet is free! and for those NON-Us residents that have been baned from all the good stuff -like me!- heheh www.replay.com has great STUFF!! and no its not on the states! so we CAN download it, and THEY CANNOT close the site. life is good... sorry mr.Clinton i still get sekurity even though im not at your door... B.T: no i do not work nor have anything to do with REPLAY.com ok im just a satified ... user, and i think the that for those that still don't know about it should check it out.

Re:Of course, the problem with this is... (0)

Anonymous Coward | more than 14 years ago | (#1733748)

You can use it to encrypt your zillion-bits PGP keys for all your hard-drives, so this is basicly a crypto for keys, granted it works which is not that simple.

Re:Some thoughts on encryption (1)

drig (5119) | more than 14 years ago | (#1733749)

The first thing that amazes me is that we don't have a good random number generator in hardware. For various reasons you cannot build a perfect one in software - software has to be deterministic. But you can in hardware.

It's really difficult to write a software package that contains hardware :)

Anyway, Intel's Willamette chip has a hardware RNG. I think Intel will be supporting it on Linux.

you need a completely *random* key (1)

Anonymous Coward | more than 14 years ago | (#1733750)

Another issue that I have not yet seen mentioned in this discussion about OTPs is that you need a completely random key. /dev/urandom isn't good enough, /dev/random is. Massaging an audio file like the documentation discusses would not really be good enough. Using, for example, rand() to generate a key, would be laughably insecure. Using md5, DES, or any other hash/crypto algorithm would be only as secure as that algorithm. Thus losing you the benefits of an OTP, but leaving you with all the logistical problems.

If you can find a way to generate and securely distribute an OTP (e.g. sending it by courier to your embassy, or handing it to the captain of the ship you want to communicate with while it's at sea), it may be a good idea to encrypt the key and possibly even the messages you send anyway. This doesn't reduce the security of the scheme to the security of that encryption, because you still want to obey all the normal rules you would with an OTP. But it does add an extra layer of security, in case the OTP is compromised - which is a risk, considering that both parties will need to store the OTP on disk/tape somewhere. (and remember how everyone always tells you not to write down your passwords).

Re:Some thoughts on encryption (1)

QuMa (19440) | more than 14 years ago | (#1733751)

How about using the least significant bits from /dev/audio (making sure the mic is a full volume).
Even the computer's fan should be enough to make this unbreakably random.

Snake Oil (1)

Edgy Loner (44682) | more than 14 years ago | (#1733752)

This does'nt look too good. 1. For all of the already posted reasons about why OTP's aren't practical. 2. It's not even a good OTP implementation. It looks like it uses rand() for it's entropy. The last time I checked rand() wasn't good random enough even for games let alone crypto! Like a bunch of people already said, use /dev/random. Maybe run that through a good whitening scheme and use that for your OTP. One of the recent Phrack issues had a good discussion of whitening random data streams.

Re:MAE LING MAK and a modern world view (0)

Anonymous Coward | more than 14 years ago | (#1733753)

Yeah... something happened. Like FRIDAY. ;) (Actually, I do most of my MAE LING MAKking during company time.... hee hee hee...)

And Slashdot was down for huge expanses of time... only in the last couple of days.

Returning to an earlier thread that I saw on another board, any system administrator that ever lets their system go down should be terminated- downtime is not acceptable. Unix is old and unstable, and slashdot should not use it. Windows NT4 with service pack 5 is extremely stable- I use it constantly and it has not gone down in weeks... all you linux lusers are talking through your hats- I personally haven't installed it myself, but there is *NO* way that it can be more stable than something commercial like windows. Slashdot should be running on NT if you want to avoid downtime. Anyone who can't get something as simple as NT working and ready for a news site like slashdot in under 24 hours should be fired immediately... same thing for down time. Get rid of bad administrators.

But they say to use the OTP "over and over again." (1)

jcorgan (30025) | more than 14 years ago | (#1733754)

I don't recall specifically, but isn't the unbreakable security of a OTP due to the fact that a given key is only used once?

The documentation states that once a key file of a given size is generated, it can be used "over and over again." If I remember correctly, an opponent who has two ciphertexts that were XORed with the same "OTP" can trivially recover the key (though I forget how.)

Hmmm, I should go dig out my Applied Cryptography. It's covered in there somewhere.

Re:Why people don't use one time pads (1)

Anonymous Coward | more than 14 years ago | (#1733755)

Then you have to worry about only using the pad once. If you use it twice, your message is totally toast. During WWII, a lot of traffic was gathered this way.

Just twice? How?

Here are two strings of numbers. I obtained them by xor'ing the ASCII of two English text messages with the same sequence of random numbers. What are the plaintexts?

[171, 61, 38, 69, 203, 212, 243, 134, 223, 99, 169, 83, 117, 243, 27, 89, 194, 8, 227, 145, 248, 41, 131, 25, 77]

[177, 58, 56, 22, 131, 216, 242, 195, 139, 98, 191, 83, 103, 242, 12, 10, 197, 77, 237, 155, 229, 62, 194, 13, 92, 10, 255, 249, 28, 211]

Even if you can't do this, in general I take your point, though.

Alex.

Compressed files as random data? yeah right... (1)

Vomjom (62059) | more than 14 years ago | (#1733756)

One command will get a user the compression type:
file
All compressed headers are the same per compression type

This guy is an idiot (0)

Anonymous Coward | more than 14 years ago | (#1733757)

From: http://www.csuglab.cornell.edu/Info/People/jcr13/H ardenedCriminal/doc/sogood.html "As of right now, all known algorithms for prime number factorization are quite slow. They are all reducible to an algorithm that tries every possible factor. So, given a large number N, if you know that N has two factors, you can find them by trying to divide N by every number up to N/2. You'll eventually find one of N's two factors this way, and after dividing, you'll have found the other as well. But, there's nothing to say that you won't have to try all possible factors, and there are N/2 of them, so running time of the algorithm is proportional to N, or the size of the number you're trying to factor. To make the encryption keys harder to crack, you simply use a larger N. A running time of N doesn't seem bad (seems polynomial). However, if you look at the problem as one that takes N as input in binary form, and N is represented by X binary digits, then the running time of the algorithm is really 2^X, or exponential in the input size. This is a *very* slow algorithm--when you increase the input size by 1, the running time doubles. There are algorithms available today that make slight improvements on the running time, but there are no known algorithms that don't have exponential time bounds. Modern cryptosystems rely on the fact that exponential algorithms take (almost literally) forever to run. For instance, if you're using a 128-bit encryption scheme (N is less than 2^128), even if your computer system could check one possible factor every clock cycle (at 500 MHz), it would take your computer 2*10^22 years to run the algorithm. That's a very long time indeed."

signs of the apocalypse (1)

~spot (5023) | more than 14 years ago | (#1733768)

First the (impending) release of Command and Conquer 2: Tiberian Sun, then the suggestion that /. should run nt. we might not make it to y2k... ;)

Run, don't walk, away from this program. (1)

Paul Crowley (837) | more than 14 years ago | (#1733769)

Anything that claims to provide a "one-time-pad" for an ordinary PC always provides terrible security in practice. Except under very special circumstances that ordinary users never meet, OTP's are inherently bad security since we don't spend much time exchanging gigabytes of key across secure channels.

PGP is good. PGP works. Use PGP, or it's compatible and free friend GPG.
--

NSA and quantum computers (1)

CiXeL (56313) | more than 14 years ago | (#1733770)

What do you bet the NSA releases the encryption control as soon as they develop decent quantum computers? Remember the military usually get to play with the new tech toys first.

Only uncrackable if factoring numbers is hard (1)

Anonymous Coward | more than 14 years ago | (#1733771)

If you make factoring numbers easy either through an algorithm that the people outside the TLA's haven't found yet or through quantum computing (Which reduces the problem to a linear timeframe) then cracking public keys becomes a simple matter no matter how many bits you use in your key. I suspect that the TLA's have either an easy-factor algorithm or quantum computers (Or both) and that all this howling about encryption is a red herring.

What One Time Pads are good for (0)

Anonymous Coward | more than 14 years ago | (#1733772)

One-time-pads are good for encrypting session
keys. For example:

1) Generate 1.44MB of random data
2) Make floppies for each site.
3) Send (via trusted courier [1]) the floppies
to each site.
4) Start each session with "seek n (random)
bytes into the OTP and use the next 16 bytes
as the key for this session.

5) Replace the floppies once a month.

Ok, how badly did i blow it? I read Schneiders
book, honest!

-- cary

[1] The hard part.

Hard Cryptography & distribution (1)

CiXeL (56313) | more than 14 years ago | (#1733773)

I dont see whats stopping anyone, why doesnt anyone create a super strength RSA encryption program based on the pgp source with incredibly high prime numbers and dump it on a number of free geocities sites or into warez channels so it gets spread all over the place anonymously. I mean, fuck the gov't.

rand() vs /dev/random (1)

cdlu (65838) | more than 14 years ago | (#1733774)

problem with /dev/random is they want it portable to all OSs. Windows and Macintosh have no equivalent of /dev/random (though for some reason its always been void on my computer...but then again, I never worked very hard to configure my computer and set everythign upproperly :)). If all OSs had a standard decent randomiser then it could be changed.

Though it seems to me that web-radio is a good source of randomness, especially considering internet latency sometimes, and occasional static.

just my 2 cents (add tvq and gst if in qc)
Load More Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...