Slashdot Mirror
When Pretty Good Privacy Isn't Good Enough
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. :-)"
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.
"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)
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.
/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.
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
Using OTP is easy, whats hard is generating the pad and getting it to the other recipient.
or how about having some form of monitor to detect retarded first post message like this then when finding it sending a barrage of DOS attacks at them? heh that would be nice, little immature but very suitable for the immaturity of these people.
some peoples children
Nor is it required to check every number up to the sqrt(N) since it's only required to check against the known primes upto sqrt(N). For instance, there are 168 primes up to 1000. To factor a number upto 1,000,000 into its primes requires checking against only the 168 primes, albeit you have to have a list of the primes upto 1000. However, for very large N, there are algorithms that compute the probability that a number is prime rather than having a complete list (though I suppose the NSA could afford to keep a list of primes around somewhere). To factor a number upto 100,000,000 into its primes would require checking no more than the primes upto 10,000 (sqrt(100,000,000)=10,000). There are 1229 primes upto 10,000. All this is not to imply that prime factorization is not a hard problem, especially for very large N. However, it does underscore the HardEncrypt author's lack of rigor in the analysis. User beware!
Anyway, if I had sensitive data I'd toss my fortunes with PGP, which rests on the security of RSA and IDEA, assuming no other protocol failures (which should be flushed out as the code is available for inspection).
I challenge anyone demostrate that this modified scheme is insecure.
There are two main reasons why you can safely eliminate Step 1. Number one, many of the previous posts have successfully demonstrated, beyond any reasonable doubt, the author of HardEncrypt to lack necessary crypto expertise. Number two, even if he'd had that expertise, OTP schemes are not practical anyway. To elaborate, consider the following points:
Are we engaged in a theoretical discourse here, or are we discussing a practical matter? The theoretical aspect of this discussion was closed long time ago. The verdict? Truly random one-time pads provide for unbreakable encryption. Note that all comments made Roblimo about NP-hardness, NP-completeness, or undecidability of the problem are irrelevant, as one of AC's rigthly pointed out. So much for the theoretical foundation.
As a practical matter, who do you think is going to try decrypt your piddly emails? For any organization but NSA and its international counterparts, as well as some major corporations, the task of cryptanalysing your PGP-encrypted mail is well beyond its budget. Now, try to think in terms cost-benefit analysis. For all intents and purposes, if any powerful institution were ever to get really curious about the contents of your emails, it would be much cheaper for them to ask you nicely to surrender the key. I mean, real nicely.
The bottom line is, use PGP and get a copy of Applied Cryptography by Bruce Schneier, if you haven't already done so.
Sorry,
I realized to late That I overgeneralized.
I really meant that I thought my article were more important than SOME slashdot articles posted at the same time.
Sorry I didn't post them.
You will find them at
http://www.pureiso.com
in the news section.
Bringing this post up further.
(remove nospam for email)
I preface this with - I know very little about
this subject.
Suppose the following:
We are interested in encrypting messages, not
whole disk drives. One uses some random source
(/dev/urandom?) to make a CDROM OTP of about 600
MB, which should cover most messages and data
file sizes. Now make a second CDROM containing a
series of random indices. Give by secure (ie
hand) the 2 CD's to the counterpart you will
be exchanging messages. Now encrypt messages
using the OTP, but starting at a different point
in the pad as determined from the random indices
on the second CD. Does this message allow you
to continue to use the same 'OTP' for a very
long time without compromising the use once
principle? (This assumes that you can store
the CD's securely).
Thanks
LB
I find it hard to believe that a general compression algorithm will compress a given file so perfectly that a good cryptographer won't be able to find correlations. The only way to get perfect compression would be to optimize the algorithm for that particular file. Now if you compress it and then encrypt it with a good block cipher, that's a little better, but I don't think you'd really be better off than just using the block cipher directly on the plaintext, after first compressing the plaintext. If you want good random numbers generated in software the Blum Blum Shub generator does a good job (see Applied Cryptography) but it's pretty slow.
None of which matters if you have the key.
The problem with most "uncrackable" schemes is that they do not dedicate the same resources to key management as they do to theoretical power. Key management is *THE* hard problem in cryptographic systems, and the #1 way to break a system. In practice, something like BlowFish with a 128-bit (or if you're paranoid, 256-bit) key is pretty much unbreakable today, and public key encryption methods are used to do the "hard part" (key management to exchange keys for the "real" encryption method), thus reducing the possibility of it being broken by the expedient of reducing the amount of crypto-text available to be attacked.
Of course, there's always the possibility that some quantum leap in mathematical knowledge will make asymetrical (public key) algorithms unsafe. But symmetric algorithms like BlowFish do not share that quality, and it is a LOT easier to distribute keys for BlowFish than to distribute keys for One Time Pads (said keys which must be the same length as the text to be encrypted/decrypted).
-E
Send mail here if you want to reach me.
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.
:-). Voice is likewise highly structured.
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
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 only good weather is bad weather.
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.
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...
Geeky modern art T-shirts
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
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.
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.
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...)
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.
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.
"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."
Using von-neumann computing, this is true. However, there is a quantum computing algorithm to factor large numbers (you take a quantum superposition of all possible numbers, raise a test integer to that power modulo the number you want to factor, do a fast fourier transform on the result, and add one to the periodicity that jumps out of the noise. There's a good chance that you have a factor, and if not, you can try again.). I believe this algorithm has actually been run on an avagadro sample of quantum computers (otherwise known as molecules in an NMR machine) to factor the number 6. Of course, even if QC obeys Moore's law starting now (and I suspect that QC's doubling constant will be longer than 18 months), there are still a good 20 years or so before it gets to the point of factoring 4096-bit keys, and you can't distribute quantum computations to hurry that up any.
Anyway, the eventual number of atoms needed is theoretically 1 per bit in your computer. The algorithm requires three full-width registers, and any reasonable implementation of QC will take at least triple redundancy and error correction, so that's 3*3*4096=36864 atoms. I would be happy to provide this quantity to anyone who asks.
Preferential Voting: easy as 1-2-3
And (3) it's much much harder to wipe the data so it can't be recovered than you think. OTOH, if all you're hiding using this elaborate mechanism is a secret lover, you probably don't have to worry about that level of effort applied to breaking your security. Unless you secret lover has a secret lover that you don't know about, maybe...
The output of /dev/random is 8 bits. (0-255) When you take the mod 95, you get results like this:
-------------------------------
0-94 => 0-94
95-189 => 0-94
190-255 => 0-64
Aag... HTML is no good for aligning things... without <TABLE>s!!!!
This is very bad. Note that the rage from 0-64 is represented 50% more than 65-94! This will seriously distrupt the randomness of your data. In fact, I'm quite surprised your SD was only 0.1, though I didn't do the math myself. At any rate, the correct way to produce values from 0 to 94 from /dev/random would be to %128 (or &127) to cleanly extract 7 bits, and discard values above 94. Then your output would hold up in the histogram.
If you do try this, please let me know at the above email address. I hope I can restore your faith in /dev/random, as it actually is quite good.
My Freakin Blog
...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.
Geeky modern art T-shirts
I love you, man :P
Three Letter AGENCY! Where did you get "acronym" from?
This is one of the oldset encryption schemes around...
don't i feel stupid
Insert mind here.
I hack'd together a small program to see how random your average sound file really is. I had it make a nice graph of relative frequencies The graph looked like this: 0 (byte values) . . . .. .... ................ - this spike = 127 ..... ... .. . . . 255 output from rand() looked like this: 0 (byte values) ......... ......... .......... ......... ......... .......... ......... ......... ........ ......... 255 So unless you sample true white noise this is not a good way to get random data. Once heard a rumour of a CIA system which used sampled cosmic background noise, which is way more secure.
You can already go to http://www.replay.com (a Dutch site) and download all the crypto you'd ever want. The problem is that we can't put encryption into the Linux kernel, because the Feds then would shut down all the U.S. Linux kernel mirrors as "illegally exporting armaments" (sheesh).
-E
Send mail here if you want to reach me.
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...
The mark of a good encryption algorithm is that even if the opponent has seized your computer and has the complete source code to the encryption algorithm (perhaps by reverse-engineering the program), he cannot crack your crypto-text without the key.
In other words, security by obscurity does not work in reality, so you might as well use well-tested algorithms that are provably secure (well, secure at today's state-of-the-art anyhow, I make no promises for fifty years from now!). Design of crypto algorithms is HARD. It's very easy to make mistakes. So it's best to use algorithms that are well-known and that have been extensively analyzed, because even experts make mistakes (hmm, was it RC4 that had the weak keys?).
-E
Send mail here if you want to reach me.
Looks like the one time pad strikes again!
/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.
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
Happy ciphering!
LILO boot: linux init=/usr/bin/emacs
I have no faith in the good intentions of my government, but I do have faith in the academic community's ability to successfully analyze mathematical algorithms -- which is all that encryption is.
With symmetrical algorithms 256 bits gets you unbreakable for the next 50 years or so (depends on the algorithm, of course, but I'm thinking a good one like one of the AES finalists). With assymetrical (public key) encryption there is a bit of doubt there -- the public key does include information that could be used to derive the private key, but it would require a quantum leap in our ability to solve certain hard mathematical problems.
In any event, if I'm a national government and I want to ruin your life all I have to do is flash my FBI batch at your local sheriff's office, tell him that you are a drug trafficer, and then said sheriff can immediately burst into your home and sieze your property and all bank accounts. You then must prove that your possessions were not bought with drug money in order to get them back, but how are you going to do that without money to hire a lawyer (because they siezed your bank accounts, remember?). And how are you going to do that without a job, because said deputies burst into your employer's office, told them you were a drug dealer, and seized your computer at work, thus resulting in you being fired? We already have a police state, it just tries to be polite about it except when dealing with what the majority thinks is the "scum of society".
-E
Send mail here if you want to reach me.
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.
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.
Well, a couple of problems:
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...)
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.
This is for secure communication, not a way to keep your storage secure.
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.)
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
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?
I know this is hard to believe but get ready for a world far different from the one we grew up with in the 60's and 70's. The best silicon is going to show up at Toys R Us and the minions of the central authorities will get to play with it after they've put in their $10 deposit. OK, I'm exaggerating slightly but this stuff is being driven by economics, not enlightened despots. The same forces that bring frenetic focus to 3D graphics today will affect the development of all useful advanced technology, including the so far largely mythical quantum computer.
Personally, I think the most insidious influence reducing peoples inclination to secure their own privacy is glib cynicism. The tools are there if it matters but if you don't want to bother you can claim, "they could use their superior technology to beat anything I'd try"
Right, but this is a far cry from claiming that the NSA can do factorizations in seconds.
It comes down to your own personal security criteria, but I'd rather trust a problem that bright people have worked on for centuries (factorization) than one which involves newer (and thus less well-understood) math. That's my personal take.
[
No, not quite. It's not safe, for example, to use the same key twice with RC4: you could do exactly the same demonstration, since RC4 uses the key to generate a stream of pseudorandom numbers, then XORs the key with your message.
It's safe to use the same key many times with a secure block cipher, though you need to worry about chaining modes to avoid providing the same input block twice. It's safe to use the same public key for years with the same caveat.
No, the real take-home message, I'm afraid, is that designing secure cryptosystems is really difficult and you should know a lot about crypto before you field one. Your best bet is still to use PGP.
--
Xenu loves you!
I have had a cursory look at the GenKey source, and I have only a passing understanding of cryptography concepts, but It seems to me that this program does not unbias the source of random data. IT IS THEREFORE USELESS.
Explanation:
The One Time Pad is secure, if impractical, only if the key consists of truly random bits. If the key is a sound file, an image, a set of "random" keystrokes etc it will not be truly random. It will have statistical properties , or "bias", that will reveal part or all of your message. For example sound values tend to follow periodic patterns.
It is true that the input stream may contain enough randomness, or "entropy", to encrypt your message. But generally you have to record a large amount of data containing randomness, say audio, and run it through an algorithm that generates a much smaller, unbiased random stream.
There are some ingenious algorithms to do this removal of bias if the sources are entirely random but biased, eg. weighted coins. It is not possible to write a general purpose utility since you do not know how random your source is, and therefore how many source bits to consume per key bit. The program in question appears to mix the source bits in an ad-hoc way that seems, well, crap.
Personally, when I want some random bits I run md5sum, type a few pages of "random" keystrokes and press ^D. Out come 16 bytes that I can be pretty confident are random.
Pavlos
I believe you talking about GAK - corporate key recovery, which IS NOT a backdoor - it's a feature allowing a business to recover 'crypted info using a an additional "corporate" key. Your private key IS NOT recoverable. There was a lengthy discussion on the merits and impacts of this on Comp.Security.Pgp.Discuss - check dejanews by searching Comp.Security.Pgp.Discuss for "corporate key recovery" or "GAK".
Well, yes, you can manage one time pads for a relatively small volume of communication with a very small group of correspondents. Beyond that, key data either runs out or is accidentally used twice.
/.
/. If the government wants us to respect the law, it should set a better example.
It's not that bad. GenKeyFile just pushes the random sequence generator off to the "seed" file. I'm not sure why it's called that -- it's basically the OTP but before churning in some of the (poor) pseudo-random numbers from rand(). I agree though that people shouldn't use it. It's very unlikely that the average person can provide a good seed file.
Their code may not recycle the key, but their documentation on the website recommends reusing the key file for convenience!
I know this is highly off topic, but I have no other way to get posted I think.
/., but 3 days later they published an article about a kid beeing convicted for warez.
/. has really a lot of submission everyday. But are my submissions totally irrelevant or is there some segreation?
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
I don't remember for the others.
So, I know that
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
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
Let me see if I can improve your explanation.
d erek/certify/secret-key.protection.html
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/~sen
for more information.
[
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..
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
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.
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
That's really interesting. Thanks for enlightening me.
Lookie here Maw!!
Ted Kaszinski and Timothy McVeigh finale gawt thar emayl uhcowntz at duh big howse...
--- Generation X: The first generation to have SIG lines inferior to their parents... ---
Well, it's more that the 'near primes' that PGP uses have an astronomically small chance of having 'small' factors. The number may or may not be prime, but it isn't obviously unprime. (It's not even for instance.)
And generally if the number is non-prime, PGP encryption just plain won't work.
Not quite. A prime number is no different from a non-prime except that it has less factors. PGP can't tell if a given number is prime except by trying to factor it, otherwise it'd simply test all the numbers it generated and this whole 'near prime' thing wouldn't even be talked about.
We can't tell how far ahead of the rest of the world the NSA is. Most of their mathmeticians aren't actually working 9-5 at cracking codes, they're engaged in general research, so they've got many more people working at advancing the field than anyone else. Other mathmeticians have to pay the bills and then work on crypto in their offtime. Also, it's hard to look at the general level of math knowledge and tell how far ahead someone is. We do know that the NSA advised (IBM?) to change DES for a then-unknown reason which was only discovered years later. But, do we know when this was discovered then by the NSA? Perhaps they worked it out years earlier. But perhaps this was discovered mainly by someone curious as to why the S-Box design was dictated by the NSA. If unguided, perhaps it would have been fifty years before that was discovered.
We don't really know what state of the art is for the NSA because they tend not to publish. They also hire a lot of civilian mathmeticians without saying precisely why. Are they perhaps taking the one who seem closest to actually figuring something important out and leaving the non-crypto oriented and the less bright (and the contientous objectors who won't do government work.) to advance common knowledge?
Perhaps prime-based crypto is better to use than one of the newer non-prime algorithms simply because of the ammount of peer review, but we don't know if we're 2% or 95% of the way to being able to trivially factor large numbers, trying to guess where the NSA is seems even harder.
Well, if you're outside the US then US law can't touch you anyway, so you may as well just download it and look at it.
Right. US law just nails the software authors' asses to the wall instead. Remember what happend to Phil Zimmerman...
---
DNA just wants to be free...
More to the point, if you use a OTP (emphasis on the "ONE"in One-Time-Pad) more than once, you compromise it.... the whole concept as presented in this site (as in "use the same OTP many times") is fundamentally flawed.
I wonder if it is a troll?
S
Have fun . . .
-- Reverend Vryl
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.
yeah, yeah . . . preview before submit . . .
It ain't that exciting a link anyway.
-- Reverend Vryl
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]
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.
Mea navis aericumbens anguillis abundat
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 = ?
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) verify that the RNGs are random enough?
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.
Couldn't this qualify as informative?
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 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.
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.
/* The beatings will continue until morale improves. */
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.
source is available.. show me the backdoor !
Do you have any proof? Any articles to validate your point. Did they back door commercial PGP or PGPI?
so, it encrypts keys.. hmmm
well, that sounds pretty cool. wonder why no one thought of this before
Insert mind here.
hyuk hyuk.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
Hardware RNG's do exist, but why are they not in more common use?
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
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 folks.
Cheers,
Ben
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
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.
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).
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.
Well, I meant for it to be informative, however it IS still not related to the topic at hand, and hence "offtopic." A right and a wrong don't make a right... do they? I think they make a wrong, or a neutral. MAYBE they do make a right, but the right's right there with the wrong, right? (Wow, posting as an Anonymous Coward is FUN, I can saw WHATEVER I want now, woohoo! AC from now on!)
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.
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.
I wrote parts of this stuff
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.
--
Infuriate left and right
The web page says that OTP is NP-complete, NP-hard, undecidable, ...
This is bullshit. It can't be cracked (of course assuming all the necesary things) but that doesn't make it part of those well defined classes of problems. It's simply unsolvable for the same reason that the following problem is:
x+y=4. What are the values of x and y?
(Actually, OTP shares the property with this problem that all answers are correct, so you don't know what the intended one was)
NP-completeness is irrelevant.
Thanks, plambert, for making such a convincing demonstration.
The take-home message here is that it is generally safe to use the same key a number of different times with a conventional secret-key system, but not safe at all with a one time pad.
LILO boot: linux init=/usr/bin/emacs
There are a couple of issues for you to think about: 1. you have to protect your keying material. I might simply steal a copy of your disk and deal with all of your future traffic. 2. It is VERY hard to create truly random streams of numbers. Virtually any program will give you a pseudorandom stream, not good enough. Physical events are subject to sampling bias or are simply not as random as you think. OTP is used for the most secure diplomatic communications by some contries but the pads are protected by guards, guns and gates. You have to be able to destroy your key material before being overrun. Factoring public key material is not feasible for keys over a couple of thousand bits. If you are really paranoid, use file encryption with a shared private key (the key has gotta be good). The IDEA algorithm used in PGP should last through the end of time (10^25 years or so). Get a copy of Schneier's Applied Cryptography!
The OTP distribution problem is simple to solve if you are willing to compromise on the "oneness" of your pad. Just use a very big highly random pad which you distribute to your partners in freedom (totally secure distribution is not essential), and then apply varying transformation functions to it to generate an unlimited number of Nearly-OTPs.
The transformation functions should be parametrized by N*(1:M) keysets where M is very large: for example, if M is the number of bytes on a publicly-available music or games CD and N is the number of CDs you decide to use, then the distribution problem boils down to sending N names of CDs from Bob to Alice, plus the name or number of a transformation function if you choose to vary that as well.
That's a trivial amount to distribute securely, even over a low-bandwidth covert channel, and the largeness of such an M creates a combinatorial explosion that would give the biggest of cracking computers something to think about for a long time. Consider the number of different CDs in the world (and MP3s!) and the computational task of combining them even for a trivial linear correlation, then consider that N is unknown to the cracker, and then consider that arbitrary transformations can be applied to the keysets first to render linear correlation fruitless: the problem becomes utterly infeasible to solve by brute force, not because of strong cryptographic properties but because the universe of key-seeded transformations on the underlying pad is limited only by the imagination.
So, if you're willing to be pragmatic about it, (N-)OTPs are live and well despite a theoretical key distribution problem --- ie. the ability to dereference from a name to a keyset means that the CD publishers perform the bandwidth-intensive distribution for you.
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
The audio file they use to generate the key-file will be converted into a a key-file of about the same size. (They remove the static headers.) As they say, audio files are going to contains noise and be difficult to reproduce exactly. However, an audio file is nowhere near being completely random. If it were completely random it would be impossible to compress, for example. If the best possible lossless audio-compression algorithms could compress the audio-file down to, say, 1/64 size, then obviously it would be enought for the attacker to guess the compressed file, expand it and generate your key.
This is mostly of academic interest, though, since guessing 1/64 of a 128KB audio file is completely out of the question. But it does show that their claims are not completely true.
A better description of the system would be a Pseudo-OTP, using a pseudo-random number generator with a very large initial seed. This could still be a secure system, assuming the PRNG they use were any good.
Looking at the source code (go OSS, go!) it doesn't look particularly effective. It "randomly" picks bytes from the seed file to output. It then xor's it with a "random" byte. These "random" bytes are from the C rand() function. This is done 5000 times, the buffer written to disk and rand() re-seeded from a key-file byte.
I'd say that the GenKeyFile program doesn't do anything useful to the seed file. Here is how I would recover a good portion of the plaintext:
Since the seed for rand() is small, we can loop through all the possible guesses without any trouble. Step 4 will return bytes of the form C ^ r where C is the cipher-text and r is the bytes we are using from rand(). C will be of the form P ^ S ^ r' where P is the plaintext, S is a byte from the seed-file and r' is a byte from rand() used in the encryption. If we guessed the seed for rand() correctly we'll have output 5000 bytes of the form P ^ S ^ r' ^ r = P ^ S.
In other words, it is easy to completely strip away the pseudo-random mixing. The distribution of bytes in the seed file (assuming it is sound) will be far from uniform. In fact, it will probably contain a lot of 0's, especially if it is your own voice, as they recommend for beginning users. Uncompressed audio tends to be sampled at 16 bits, and for large parts it will have the high byte zero (low volume). In other places it will have either the low byte small (really low volume) or the high byte small (fairly low volume). All in all, a lot of the S values can be expected to be zero. This menas that we can:
This is where you would have to start doing mildly tricky stuff like looking at the actual probability distributions involved, etc.
Short version: Don't use this stuff.
Slightly longer version: This looks OK, if you just use a good seed file. A compressed audio file would be a start, WAV files are completely out of the question. Actually, you should just dump as many bytes as ou need from /dev/random and make that your key-file. Now we just have the usual unsuitability of the OTP to practically anything to contend with.
Logi - I can do anything, but not everything.
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.
...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).
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
There are always four sides to every story: your side, their side, the truth, and what really happened.
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.
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...
My usual seat in the cluetrain is at A HREF="http://pub4.ezboard.com/biwethey.ht
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)
-- Reverend Vryl
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. Modern cryptography is very, very good, and there's no reason to fool around with one-time-pads and pseudo-random number generators.
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.
Citizens Against Plate Tectonics
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.
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
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.
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????
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.
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.
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.
Go read my top-level post for this article: "The Value of OTP"
It's not utterly useless, just not very useful for the typical person at this point in time. Diplomats, spies, business executives, politicians, criminals, revolutionaries, and terrorists could find it invaluable (not necessarily a good thing for humanity in general...) and I think that in the long term it could become the only useful form of encryption and possible the base of all commerce.
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.
/* The beatings will continue until morale improves. */
Thermal noise is so easy to generate (one transistor, a couple of resistors and optionally a diode attached to your parallel port is all you need) that achieving good randomness isn't a problem.
OK, so the noise may be pink rather than white, but you can whiten it by a variety of means, and anyway, pinkness doesn't matter as far as OTP algorithms are concerned: you still can't infer the next bit in a sequence as long as your key bandwidth is (substantially) greater than your data bandwidth. Given that proviso, knowing that the noise is pink doesn't help the cracker at all.
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
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.
Of course, you don't use public key encryption for anything other than key exchange. The speed is not really an issue. Symmetric encryption is much, much faster - easily able to cope with the loads you talk about in real time.
If you really did /dev/random % 95 I think I see your problem - that's obviously going to skew your distribution (whatever you read is going to be a number of bytes, and thus a power of two).
As if the above weren't difficult enough for a cracker, note that you can cross over to the more politically-correct world of symmetric and PK cryptographic algorithms by using either of these as transformation functions in the N*(1:M) N-OTP scheme.
Cascading more than one such algorithm together can produce a weak result, but this is not the case when you cascade one with an ideal OTP (it creates total obscuration of any cryptoanalytic weknesses in the applied algorithm). Of course, it would be pointless to do this in an ideal world, cryptographically speaking, since in theory you cannot improve on a OTP. However, N-OPTs are not ideal OTPs, so such algorithms (especially PK ones) can significantly increase the functional parametrization space.
As always though, remember to keep the key bandwidth substantially greater than the data bandwidth, eg. sample any physical noise infrequently. [Don't forget to attach an alert to your noise generator too so that you know when it stops making a racket: trannies, diodes and your parallel port do die occasionally, and that can be cryptographically embarrassing.]
"The question of whether machines can think is no more interesting than [] whether submarines can swim" - Dijkstra
With the invention of high speed access (DSL, Cable, Ethernet) the internet becomes an invaluble resource. Head over to ftp.netscape.com, download a god auful old version of netscape in mac format, and use it as your key. It will alwas be around, even if netscape go backrupt you will still be able to find it somewhere on the net.
Personly, im using a 12mb porn video from one of my favorite sites that im keeping on a PGP encrypted disk. its a large site, so im sure its not going under before the next time I get a wild hare and chnage encryption schemes to thow off the guys I hear breathing on my line.
Also to deal with the size issue, cant it use looping data? i.e. if your key is taco, cant it just XOR with tacotacotacotaco untill it reaches the EOF of the file to be encrypted? Granted its a little insecure, but think of the odds if your encrypting a 2gb disk with a 100 meg key?
symetrix. We are building a religion, a limited edition.
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).
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.
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.
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.
Babies are cute because they have to be.
One command will get a user the compression type:
file
All compressed headers are the same per compression type
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."
Well, if you're outside the US then US law can't touch you anyway, so you may as well just download it and look at it. For all practical purposes it sucks anyway.
Nor that this particular article was pointless. But I have encountered
the same problem as you.
I think one of the problems you might be having is that, if you're
submitting your articles as an AC, Rob's trained squirrels are likely
down-grading them right off. You'll note that very few articles are ever
attributed to "Anonymous Coward."
That being said...
I used to use a Slashdot "account." But after submitting numerous
articles that I felt to be important, and seeing reams of completely
irrelevant articles published in their place, I began to tire of the
exercise. Then when I submitted an "Ask Slashdot" item that I felt to be
potentially particularly interesting to geek computer users, and was very
important to me, and seeing that go unpublished as well I stopped
bothering with the login nonsense.
I still read /. regularly, tho. And I even continued to submit the
occasional article that I felt to be particularly important and timely.
None of them were published. Some of them finally did appear, frequently
days later, submitted by another person.
So I no longer bother submitting news items to /. at all. Regardless of
how interesting or important I find them.
Since I know for a fact that /. misses many important or interesting news
items, or that I may not see them for perhaps days after they appear
elsewhere, and coupled with the site's regular performance problems and
frequent outages, I no longer rely on it as my primary "news for nerds"
news site anymore, either.
there was a long-running recent thread on the cryptography mailing list about /dev/random which might be germane to this. See http://www.mail-archive.com/cryptography%40c2.net/
-- God is silent. Now if we can only get Man to shut up.
>Links to the recent MAJOR busts in the warez >scene on groups like Razor1911, Hybrid, >Fairlight, Paradigm, Origin (NY Times, yahoo,ZD) I haven't been able to find the articles. Any help?
>Links to the recent MAJOR busts in the warez scene on groups like Razor1911, Hybrid, Fairlight, Paradigm, Origin (NY Times, yahoo,ZD) I haven't been able to find the articles. Any help?
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... ;)
"and no, im not the spot working for Transmeta, although i wish i was..." -- ~spot "i'm the epitome of public enemy..."
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.
--
Xenu loves you!
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.
http://www.livejournal.com/users/cixel
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.
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.
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.
http://www.livejournal.com/users/cixel
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)
OFTC: By the community, for the community