Forgot your password?
typodupeerror
Encryption Security

When Pretty Good Privacy Isn't Good Enough 169

Posted by Roblimo
from the let's-not-confuse-codes-with-ciphers dept.
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. :-)"
This discussion has been archived. No new comments can be posted.

When Pretty Good Privacy Isn't Good Enough

Comments Filter:
  • by zCyl (14362)
    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.
  • Yes, its dependent on the fact that a given pad is only used once. But whats more important is that the pad is unpredictable. If I create successive 1024-bit pieces of the pad by counting up in binary. using a 1024-bit wordsize, and I start at a 'random number', I will not use the same key twice, but the key is predictable, and so its bad.

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

    Using OTP is easy, whats hard is generating the pad and getting it to the other recipient.
  • 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
  • by thoth (7907)
    It looks odd the author wrote his own XOR function, what is wrong with the ^ operator?

    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've seen a lot of criticism posted here. Things are not as bad as many posters would like you to imagine. The proggy is quite usable. Just make sure to encrypt all your HardEncrypt'ed messages with PGP and you will be OK. So, it has to be a two-step process:
    1. Use HardEncrypt to encrypt your message.
    2. Re-encrypt the message obtained at Step 1 with PGP.

    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:
    • Audio files are not random. Good one-time pads are generated using machines based on nuclear radioactive decay. This process is believed - but not known! - to be truly random (whatever that means) or, at least, unpredictable. Audio files don't even come close.
    • Key management is a bitch. It always it. With HardEncrypt, it is a bitch of epic proportions, all clueless comments to the contrary notwithstanding.
    • C'mon guys, get real!
      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.

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

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

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

    If they had used a semirandom source (like audio or key click timings or something), and THEN used a solid cypher to encrypt it to produce the one-time key, I would be much happier.
  • 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... ;)
  • Among the errors on their W hy it's uncrackable [cornell.edu] page is this bit:
    So, given a large number N, if you know that N has two factors, you can find them by trying to divide N by every number up to N/2. You'll eventually find one of N's two factors this way, and after dividing, you'll have found the other as well. But, there's nothing to say that you won't have to try all possible factors, and there are N/2 of them...

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

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

  • by Anonymous Coward
    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.
  • While this may still be a lot of numbers, it's no N/2.

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

  • "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.
  • I wish you weren't anonymous so I could respond directly, but oh well. I hope you read this. :)

    The output of /dev/random is 8 bits. (0-255) When you take the mod 95, you get results like this:

    /dev/random => /dev/random % 95
    -------------------------------
    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.

  • ...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.
  • Three Letter AGENCY! Where did you get "acronym" from?
  • This is one of the oldset encryption schemes around...

    don't i feel stupid
  • 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
  • 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
  • Looks like the one time pad strikes again!

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

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

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

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

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

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

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

    Happy ciphering!
  • 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
  • by rde (17364)
    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.
  • by plambert (16507) on Saturday August 21, 1999 @09:44AM (#1733646) Homepage
    "this is the first message"
    "now here is the second string"

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

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

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

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

    so you have:

    C1= T1 XOR K
    C2= T2 XOR K

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

    C1 XOR C2 = T1 XOR T2

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

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

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

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

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

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

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

    does that answer your question? ;-)

    --plambert
  • 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.)
  • The problem with re-use is that it provides the cracker with a way to verify a guess.

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

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

  • 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
  • Sigh, I count two uses of "K" in your algorithm. Note the prominent use of "One" in "One-Time-Pad"
    As soon as you use the pad a second time it's no longer a "One-Time" Pad...

    What you describe is basically how a stream cipher works, except that K is supposed to be continuously changing based on an initial seed from the key. If the stream doesn't change then yes it's totally insecure.

    Which isn't to say that's stopped people from using such things. Examples of such encryption are the MS SQL 7 login packet and the MS Windows .PWL file (the former it appears is intentional and the latter due to incompetence) To be fair to MS lots of other companies have marketed products that have similarly insecure ciphers.
  • 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.
    --
  • 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
  • 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.
    /.
  • Sigh, I count two uses of "K" in your algorithm. Note the prominent use of "One" in "One-Time-Pad" As soon as you use the pad a second time it's no longer a "One-Time" Pad...

    Well, that's hardly a surprise, since what plambert was demonstrating was how easy it is to break the encryption if you re-use your one-time pad.

  • 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
  • Let me see if I can improve your explanation.

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

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

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

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


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


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


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

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

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

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

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

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

  • by scrytch (9198)
    PGP is not "uncrackable", merely "hard". A OTP isn't a mathematical problem, it's a pre-established secure channel. The trick of course is in establishing that channel. And you can't reuse it.
  • by Vryl (31994)
    I don't actually believe it for a second. I think we have gone further than the TLA's (see my Everything node [http] on TLA's).

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

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

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

    -- Reverend Vryl

  • 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...

  • And the "near primes" that PGP uses have an astronomically small chance of being non-prime.

    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.

  • by MenTaLguY (5483)

    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...


    ---
  • 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
  • by Vryl (31994)
    I did not write the initial node, but I have now updated it to include TLAgency.

    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.

  • by Vryl (31994)
    here [blockstackers.com]

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

    -- Reverend Vryl

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

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

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

  • 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 [state.nv.us]) verify that the RNGs are random enough?

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

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

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

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

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

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

    I don't know how to argue this one, since "general computing" is too fuzzy a term to argue with. One could well argue that encryption in general or 3d cards have no use in "general computing." I agree it's excessively troublesome for the typical user who doesn't care if the FBI or a rival corporation is listening, or if it might be cracked in a few years. I certainly don't see how, when correctly used, it could give anyone a false sense of security, unlike encryption schemes that can be broken by sufficiently motivated groups.
  • 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.
  • 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 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.
  • In that case the key management problem is even worse, don't you think? That old annoying secure channel paradox: You need a totally secure channel to exchange the key. However, if you have a totally trusted secure channel you don't need encryption at all.

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



  • by tilly (7530)
    Hardware RNG's do exist, but why are they not in more common use?

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

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

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

    Cheers,
    Ben
  • I trust PGP for all of my encryption needs. I also trust ssh and hushmail.com.

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

  • 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).
  • I knew the theory, but I'd never seen it in practice. Pretty cool. I guess all the moderators ran out of points so I'll just add a reply, since this is about the most relevant message for this article.

    EJB
  • 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.
  • I think the real problem is a man-in-the-middle style attack, in which someone could insert a bogus Java applet into what looks like a hushmail web page. Type your passphrase and BLAM!, instant security breach.

    IMO, it's better than SSL secure webmail, but worse than PGP.

  • 1. True, but...

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

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

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

  • Greetings,
    That would be fine, I agree... The key distribution problem restricts what you can do with OTPs to a limited set of problems, but if your problem falls within that domain it's acceptable.

    However, if you do this, please for gods sake don't use this program! While the encrypt function is trivial (and bad, still, for reasons I briefly explain later), the GenKeyFile as ATROCIOUS . It makes me physically ill to think that anyone would pass that off as an OTP generation function.

    The attack on it is trivial, given physical access to the machine. (I.e. it was seized, etc.) Presuming the GenKeyFile program was used, the key file is generated using rand(), seeking through a seed file and generating the bits for the 'true' key file. Even if you wipe the 'true' key file (that gets generated by this program), but keep your initial seed file around (i.e. you're using \winnt\system32\mfc.dll to generate your random bits), here's what your security comes down to:

    32 bits of seed (for rand())
    n bits of search where 2^n is the number of files in your filesystem (or the next power of two over it).

    The assault on this method is as follows:
    For each file in the system, iterate over the 32 bits of rand(seed) space, and test the resultant file for known plaintext. (What's that, you believe that they don't know any plaintext in your document? Not true! Headers, average character counts, etc., all are telltales!) With only 32 bits of seed for your rand() function (or 64 if somehow you have an extended rand()), the keyspace is not sufficient to produce truly random output. Thus the number of matches that will generate a pattern that is similar to the expected pattern (text, images, etc., all have non-random recognizable patterns) is very small, and might be zero.

    There are four components to this 'encryption package':
    • Seed file (used to build the keyfile)
    • Generated Keyfile
    • Plaintext
    • Resultant ciphertext


    If you keep the seed file OR the keyfile around, then this encryption is 100% useless. The seed file can be found, and the rand() function gives you *LESS* protection than DES, and MUCH less than IDEA, 3DES, etc...

    Even if you've erased both your keyfile and your seed file, if the attacker can presume that you ever USED GenKeyFile to make your key data, the resultant ciphertext will be encrypted with patterns that are the result of the patterns in the seed file, mixed with the (reasonably well known) patterns of the rand() function. This patterned data can be identified by a sufficiently dedicated attacker, even w/o the original source file. Do not use GenKeyFile!

    You're *far* better off using /dev/random to generate your keyfile. If you don't have a /dev/random because you're on an OS that is insufficient, then go out and install one that has it. If you're going to go through the serious difficulties of key management under an OTP, you damn well better spend the effort to get a good random source! (In fact, if you ARE, then I would say you should get an HW random number generator, and hook that up. If you honestly have a use for OTP's, don't mess around with software like this!

    Seriously, this is snake oil. Well meaning snake oil, but snake oil nonetheless. Presuming a seized computer, and either the use of GenKeyFile at ALL , or the preservation of your used key file, this gives ABSOLUTELY ZERO PROTECTION FROM A COMPETENT ATTACKER.

    Cyberfox!

    p.s. While the encrypt program is still useful with an OTP generated from a secure source, it SHOULD be repeatedly wiping the used padbits out of the Psuedo-OTP's filespace as it goes, but it's not... Another example of less-than-stellar competency.

    Important related note: You don't use an OTP to encrypt to yourself, because you never ever ever want to keep the OTP bits a millisecond longer than it takes to encrypt it initially.

    p.p.s I can't say this enough, but I'll try one more time, please, please, please DO NOT USE GENKEYFILE TO BUILD YOUR KEY FILE!
  • 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.

    --
  • 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.
  • Not really I think. The requirements on the channel needed to transmit the key are less stringent: you just have to make sure the key cannot be read by an attacker without your knowledge (e.g. use a trusted courier who keeps the key with him at all times); if the key is read by an attacker, simply do not use the key and you don't lose much.
  • 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.
  • I'd say snake-oil.

    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:

    1. Guess the initial seed for rand().
    2. Completely ignore the bytes from rand() which would be used to pick bytes from the seed file.
    3. Construct the string of 5000 bytes from rand() which were xored into the seed data.
    4. Now output the ciphertext xor the 5000 bytes from step 3.

    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:

    1. See when our guess for the rand() seed was correct, because the distribution of the output from our little routine will suddenly be much closer to the plaintext distribution and
    2. We can actually read a lot of the characters stright from the output stream, since they will simply be the plaintext xored with 0.

    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.

  • 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).

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

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

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

    -Erik

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

    -- Reverend Vryl

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

    Why This Program Isn't Very Secure

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

    Some Good Things About This Program

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

    How to Fix It

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

    How to Lean More

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

  • 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.
  • 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????
  • There is no one best encryption protocol for all circumstances. There's no sense in using a public key protocol to protect the contents of your hard drive, and reversible encryption is not secure enough for many password systems. There's no current practical reason to use OTP for anything that does not have to be permanently and perfectly secure.

    I don't mean to endorse the general use of OTP for routine emails and such (I'll admit it sounded like I did in my original post; I cut out as obvious a part I typed about the needless expense and the typically limited need for security, but forgot to change the "it's perfectly secure! and not that expensive" contrast piece at the end). I agree that it is a waste of effort for most people.

    The point was that OTP is the only reversible general encryption scheme that is absolutely unbreakable when correctly done (dumb codes are also unbreakable, and potentially unrecognizable as well, but not general). Not expensive to break, not impossible to break in a human lifetime using modern computers, but absolutely unbreakable. It is also practical even for individuals with typical cheap home computers, certainly a needless expense for most, but a relatively small one, and still feasible.

    I certainly believe OTP will become more important in the future, as exotic computing technologies emerge and change the rules about what is intractable. They may well become the foundation of commerce as everything becomes copyable and all material products are commoditized, leaving no form of portable and quantifiable wealth.

    Your suggestion that investigators can read data from your hard drive after you've deleted them, is very interesting. I hadn't really thought of that, but the principle is still true, if you really clean up after yourself properly (which is a lot more bother than I thought, though still feasible).

    Here's a good article on the problems and how to try to get around them (it's more complicated than I first thought, and gives interesting insights into harddrive function if you have as naive a view of the encoding on such devices as I did; very interesting reading indeed):
    http://www.cs.auckland.ac.nz/~pgut001/secure_del .html
  • 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.
  • 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.
  • 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.]
  • 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?

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

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

    Anyway, Intel's Willamette chip has a hardware RNG. I think Intel will be supporting it on Linux.
  • by Anonymous Coward
    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).
  • How about using the least significant bits from /dev/audio (making sure the mic is a full volume).
    Even the computer's fan should be enough to make this unbreakably random.
  • 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.
  • I don't recall specifically, but isn't the unbreakable security of a OTP due to the fact that a given key is only used once?

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

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

  • by Anonymous Coward

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

    Just twice? How?

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

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

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

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

    Alex.

  • One command will get a user the compression type:
    file
    All compressed headers are the same per compression type
  • 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/

There are never any bugs you haven't found yet.

Working...