Re: One time pads
> Also, can your tool use floppies instead of USB keys? It's a freakin' C program that works on a file - but carrying a floppy around is so ... ordinary. > There are problems with KGB-quality attackers recovering overwritten data > which are probably much more serious for disks than flash rom, > but they're nearly universal and good shredders work well on them. Bits are overwritten by running PRNG output on them 128 times, PRNG being seeded by the data that has just been erased. We use DES in counter mode as PRNG. > You need to use each bit twice - once to encrypt, and once to decrypt. > Destroying them after the first use is a bad idea Why would sender need to decrypt known plaintext is beyond me ... sender XORs and destroys bits, recipient XORs and destroys bits. Each in their respective dongles, once. = end (of original message) Y-a*h*o-o (yes, they scan for this) spam follows: Y! Web Hosting - Let the expert host your web site http://webhosting.yahoo.com/
Re: One time pads
At 02:04 PM 10/17/2002 +0200, Eugen Leitl wrote: It is important to note that currently NMR bases systems only allow for 6 qubits. Only very recently we're getting practical qubits in solid state. . Everybody realizes that we're discussing currently completely theoretical vulnerabilities, right? Of course. But without quantum computing, you can do computations on your basic cheap computers that are secure against crackers for the expected remaining life of the universe, so your threat models are much more controllable. Obviously you still need to worry about tempest, computer viruses, cameras in the ceiling, and rubber hose cryptanalysis, but threat models that just involve someone intercepting your message aren't a problem. Quantum computing is the one thing that anybody's thought of that has a mathematically possible chance of breaking that.
Re: One time pads
At 10:52 PM 10/17/2002 -0700, Morlock Elloi wrote: > >I have a working OTP system on $40 64 Mb USB flash disk on my keychain. > > Cute. Is it available? $39 + tax in Fry's. I don't mean the disk - there are lots of those. I mean your software. Also, can your tool use floppies instead of USB keys? There are problems with KGB-quality attackers recovering overwritten data which are probably much more serious for disks than flash rom, but they're nearly universal and good shredders work well on them. > How do you prevent other applications from reading the file off your > USB disk, either while your application is using it or some other time? I don't care. No one knows about it enough to set a trap in a random PC (and if They do we're in deep shit anyway.) This is the reason for not releasing the (trivial) program. Write your own and let it be your group key ... say, 40-bits worth ? USB key disks look like an obvious target for eavesdropping in general. (They're also the best medium for re-inventing the floppy-disk virus:-) > Since you say that "Used bits are securely deleted", > does your application distinguish between using the pad to encrypt > and using the pad to decrypt (which are basically the same thing, > except for destroying the key bits the second time)? You destroy bits *every* time. The routine that reads bits overwrites them. Messages are fixed size, index into OTP file is a part of the message, each user gets starting offset assigned to avoid synching problems. You need to use each bit twice - once to encrypt, and once to decrypt. Destroying them after the first use is a bad idea
Re: One time pads
At 12:16 PM 10/17/2002 -0700, Morlock Elloi wrote: I have a working OTP system on $40 64 Mb USB flash disk on my keychain. Cute. Is it available? How do you prevent other applications from reading the file off your USB disk, either while your application is using it or some other time? That's one of the big differences between a computerized OTP and a Dead Trees (or Dead Silkworms) OTP, which is much harder for someone or something else to read without you noticing. Since you say that "Used bits are securely deleted", does your application distinguish between using the pad to encrypt and using the pad to decrypt (which are basically the same thing, except for destroying the key bits the second time)? 30Mbs are filled with distilled randomness (two video digitizers at high gain looking into open input noise, compressed first with LZW then again compressed 8:1 by taking only byte parity, then XORed together - takes several hours and passes diehard) Landon Noll has done some interesting work taking a cheap PC camera and keeping it in the dark. The CCDs try to adjust, and you get noise. Rather than compressing 8:1 using byte parity, I'd recommend using a hash function, such as MD5 or SHA, which means that every bit of the input can tweak any bit of the output. judging by the current use it will last us for decades for text messages. That's the Bic Pen model of "you'll lose it before you use it up" :-) If you're using it strictly for session key exchange, that's a lot of sessions (unless you're a big web or email server.) If you're using it for message encryption, it's obviously not much.
Re: One time pads
At 09:20 PM 10/16/2002 -0400, Sam Ritchie wrote: ACTUALLY, quantum computing does more than just halve the effective key length. With classical computing, the resources required to attack a given key grow exponentially with key length. (a 128-bit key has 2^128 possibilities, 129 has 2^129, etc. etc. you all know this...) With quantum computing, however, the complexity of an attack grows only polynomially. Hence a MUCH MUCH more agreeable time frame for brute force attacks. Good stuff, eh? The speed of quantum computing depends on the algorithm - it's generally believed that for some problems, like factoring, you can hypothetically get a hypothetically-precise-enough quantum computer to resolve in polynomial time instead of exponential, subject to a variety of caveats I don't pretend to understand, but for many other problems they're only cutting the effective number of bits in half (which is still exponentially faster than brute-force, but not *enough* exponentially faster), and for other problems they may not be a match at all. So Peter Trei's assertion that it's really only a big impact on asymmetric cryptosystems, and a much smaller impact on symmetric, is one layer deeper description than yours, and it's something that does still leave us with practical ways to use cryptography that don't include briefcases and handcuffs. Myself, I'd rather hang out at Delphi waiting for the stoned babe to give out the correct answers :-) ("If you use the right key, a great kingdom will fall...")
Re: One time pads
> Pretty much, yes. at least one "real world" OTP system assumes you will > be using three CDRW disks; the three are xored (as you say) together, I have a working OTP system on $40 64 Mb USB flash disk on my keychain. The disk mounts on windoze and macs, and also contains all s/w required to encrypt/decrypt, on both platforms. 30Mbs are filled with distilled randomness (two video digitizers at high gain looking into open input noise, compressed first with LZW then again compressed 8:1 by taking only byte parity, then XORed together - takes several hours and passes diehard) and judging by the current use it will last us for decades for text messages. OTP is now shared among group but it's trivial to have subpartitions for 1:1. Used bits are securely deleted. Works on any USB-capable win/mac. The whole USB disk can be additionally protected by either scramdisk (cryptdisk for mac) passphrase, but it limits operating platforms. The custom software was trivial to make (less than 200 C lines) and complile under codewarrior for multi-platform executables. To conclude, OTPs are easy to make and use. Plugging in the dongle to read e-mailo is extra sexy (and attracts chicks, this has been documented.) Unlike ad nauseam discussions on OTP feasibility. You guys must really be bored. = end (of original message) Y-a*h*o-o (yes, they scan for this) spam follows: Faith Hill - Exclusive Performances, Videos & More http://faith.yahoo.com
Re: One time pads
at Wednesday, October 16, 2002 7:17 PM, David E. Weekly <[EMAIL PROTECTED]> was seen to say: > As for PKI being secure for 20,000 years, it sure as hell won't be if > those million-qubit prototypes turn out to be worth their salt. I wasn't aware they even had a dozen-qbit prototypes functional yet - but even so - assuming that each qbit is actually a independent complete machine (it isn't - you need to build a machine bigger than one bit) and you had a million-unit module built - this would be equivilent to building one million (2^20, I'll be generous and give you the extra few thousand) machines each able to cross-check their results instantly (so identify if one of the million has a correct answer) This will mean you can brute force a key as though it were 20 bits shorter in keylength. even assuming you can use the usual comparison (3Kbit RSA=128 bit symmetric) this leaves you the equivilient of a 108 bit key to break - and even assuming a quantum virtual machine ran as fast as a real world one, that would take a while. Of course, if you have a machine that will break a 108 bit key in under a hundred years, I am sure the NSA would like to make you an offer.. I can't remember the last time I used an asymmetric key as small as 3Kbits. my current key is 4K and has been for some years, and my next will probably be 6K just to be sure.
Re: One time pads
at Wednesday, October 16, 2002 6:13 PM, Bill Frantz <[EMAIL PROTECTED]> was seen to say: > OTP is also good when: > (1) You can solve the key distribution problem. Its certainly usable provided key distribution isn't an issue - if it is also worth the trouble and expense is another matter. > (2) You need a system with a minimum of technology (e.g. no computers) it certainly does shine in this context - few decent encryption methods can be done with pencil and paper, and certainly by protecting the key with extra (discarded) characters, you can make the key document look innoculous indeed. Of course, indicating those characters then becomes a problem (unless you use some simplistic scheme like the second and second from last characters of each word in a specified book, but the odds of a random distribution from such is low)
Re: One time pads
at Wednesday, October 16, 2002 7:17 PM, David E. Weekly <[EMAIL PROTECTED]> was seen to say: > Naive question here, but what if you made multiple one time pads > (XORing them all together to get your "true key") and then sent the > different pads via different mechanisms (one via FedEx, one via > secure courier, one via your best friend)? Unless *all* were > compromised, the combined key would still be secure. Pretty much, yes. at least one "real world" OTP system assumes you will be using three CDRW disks; the three are xored (as you say) together, the message sent, and after the keyfiles are exhaused (or the panic button hit) all three disks are automatically wiped and overwritten (several times) with random data. this isn't a new key (although it could be used as such I suppose) but cleanup before the disks are disposed of (the docs say to incinerate the disks, or in case of an emergency, microwave them on high. There is usually a good excuse for a microwave next to the machine, which is handy for the duty guy to heat his lunch without leaving his desk :)
Re: One time pads
On Wed, 16 Oct 2002, Bill Stewart wrote: > The speed of quantum computing depends on the algorithm - It is important to note that currently NMR bases systems only allow for 6 qubits. Only very recently we're getting practical qubits in solid state. These haven't been put to any spectacular use yet. Entangling nontrivial numbers of qubits, and keeping them entangled sufficiently long with error correction (it is not obvious that both of these will scale at all), and making the system execute nontrivial algorithms (it is not really an all-purpose machine, and certainly not a computer you're familiar with) appears rather hard. Everybody realizes that we're discussing currently completely theoretical vulnerabilities, right?
Re: One time pads
at Thursday, October 17, 2002 2:20 AM, Sam Ritchie <[EMAIL PROTECTED]> was seen to say: > ACTUALLY, quantum computing does more than just halve the > effective key length. With classical computing, the resources > required to attack a given key grow exponentially with key length. (a > 128-bit key has 2^128 possibilities, 129 has 2^129, etc. etc. you all > know this...) With quantum computing, however, the complexity of > an attack grows only polynomially. Is this actually true or is it that it can scale proportionally in time and in number of qbits required? if you assume that a classic machine takes x^2 operations to break a key, but a quantum machine will take x operations with x qbits, that would have the same effect, provided you can create that many qbits. I haven't seen any papers that say that it is polynomial at all though - can you provide a reference or two?
Re: One time pads
Indeed-- I wasn't incredibly specific, and have been corrected by Bill Stewart on this. According to the November issue of Scientific American (to reference one source), Shor's Factoring Algorithm causes the resources needed to factor a given number to rise polynomially, as opposed to exponentially. Their example was that a 500-digit number, in classical computing, would take 100 million times as many resources to factor as a 250 digit number. In the world of quantum computing, when attacked with Shor's Algorithm, the 500 digit number only takes 8 times as many resources. As was pointed out, I spoke too soon. This would only affect asymmetrical algorithms, based on the difficulty of factoring large numbers. Hehe, but as Leitl pointed out, this is all theoretical, so I'm kind of shooting blind on this one. ~~SAM > From: David Howe <[EMAIL PROTECTED]> > Date: Thu, 17 Oct 2002 13:45:01 +0100 > To: "Email List: Cypherpunks" <[EMAIL PROTECTED]> > Subject: Re: One time pads > > at Thursday, October 17, 2002 2:20 AM, Sam Ritchie > <[EMAIL PROTECTED]> was seen to say: >> ACTUALLY, quantum computing does more than just halve the >> effective key length. With classical computing, the resources >> required to attack a given key grow exponentially with key length. (a >> 128-bit key has 2^128 possibilities, 129 has 2^129, etc. etc. you all >> know this...) With quantum computing, however, the complexity of >> an attack grows only polynomially. > Is this actually true or is it that it can scale proportionally in time > and in number of qbits required? if you assume that a classic machine > takes x^2 operations to break a key, but a quantum machine will take x > operations with x qbits, that would have the same effect, provided you > can create that many qbits. I haven't seen any papers that say that it > is polynomial at all though - can you provide a reference or two?
Re: One time pads
ACTUALLY, quantum computing does more than just halve the effective key length. With classical computing, the resources required to attack a given key grow exponentially with key length. (a 128-bit key has 2^128 possibilities, 129 has 2^129, etc. etc. you all know this...) With quantum computing, however, the complexity of an attack grows only polynomially. Hence a MUCH MUCH more agreeable time frame for brute force attacks. Good stuff, eh? ~~SAM > From: "Trei, Peter" <[EMAIL PROTECTED]> > Date: Wed, 16 Oct 2002 14:50:03 -0400 > To: David Howe <[EMAIL PROTECTED]>, "Email List: Cypherpunks" > <[EMAIL PROTECTED]>, "'David E. Weekly'" <[EMAIL PROTECTED]> > Subject: RE: One time pads > >> David E. Weekly[SMTP:[EMAIL PROTECTED]] >> >> Naive question here, but what if you made multiple one time pads (XORing >> them all together to get your "true key") and then sent the different pads >> via different mechanisms (one via FedEx, one via secure courier, one via >> your best friend)? Unless *all* were compromised, the combined key would >> still be secure. >> >> As for PKI being secure for 20,000 years, it sure as hell won't be if >> those >> million-qubit prototypes turn out to be worth their salt. Think more like >> 5-10 years. In fact, just about everything except for OTP solutions will >> be >> totally, totally fucked. Which means that you should start thinking about >> using OTP *now* if you have secrets you'd like to keep past when an >> adversary of yours might have access to a quantum computer. I'd put 50 >> years >> as an upper bound on that, 5 years as a lower. >> >> -d >> > Not quite right. My understanding is that quantum > computing can effectively halve the length of a > symmettric key, but that does not take it down to zero. > > Thus, a 256 bit key would, in a QC world, be as secure > as a 128 bit key today, which is to say, pretty good. > > It's the asymmetric algorithms which have problems. > > Peter
Re: One time pads and Quantum Computers
> > David E. Weekly[SMTP:[EMAIL PROTECTED]] > > > Which means that you should start thinking about > > > using OTP *now* if you have secrets you'd like to keep past when an > > > adversary of yours might have access to a quantum computer. ... > > OTPs won't help a bit for that problem. > They're fine for transmitting new data if you've already sent a pad, > but they're useless for storing secrets, because you can only decrypt > something if you've got the pad around, and you have to burn the pad after > use. Yes, sorry -- I should have clarified as "you should start thinking about encrypting data transmissions using OTP *now* if you'd like to send secrets you'd like to keep..." -- destroying both pads after transmission should be obvious. I wasn't attempting to address secure data storage. -d
RE: One time pads and Quantum Computers
> > David E. Weekly[SMTP:[EMAIL PROTECTED]] > > As for PKI being secure for 20,000 years, it sure as hell won't be if > > those million-qubit prototypes turn out to be worth their salt. > > Think more like 5-10 years. In fact, just about everything except > > for OTP solutions will be totally, totally fucked. At 02:50 PM 10/16/2002 -0400, Trei, Peter wrote: >Not quite right. My understanding is that quantum >computing can effectively halve the length of a >symmettric key, but that does not take it down to zero. >Thus, a 256 bit key would, in a QC world, be as secure >as a 128 bit key today, which is to say, pretty good. >It's the asymmetric algorithms which have problems. Yeah. What we have to do for that is start thinking about ways to apply Kerberos and similar technologies to real-world problems besides the inside-an-organization ones they were originally designed for. > David E. Weekly[SMTP:[EMAIL PROTECTED]] > > Which means that you should start thinking about > > using OTP *now* if you have secrets you'd like to keep past when an > > adversary of yours might have access to a quantum computer. ... OTPs won't help a bit for that problem. They're fine for transmitting new data if you've already sent a pad, but they're useless for storing secrets, because you can only decrypt something if you've got the pad around, and you have to burn the pad after use. Storing the encrypted secret message on your regular computers while keeping the pad locked up in the safe is unlikely to be any more convenient than keeping the plaintext locked up in the safe. I suppose you could secret-share a one-time-pad, but you could just as easily secret-share the secret message.
One time pads
hi, An extract frm this months cryptogram goes as below. On the other hand, if you ever find a product that actually uses a one-time pad, it is almost certainly unusable and/or insecure. So, let me summarize. One-time pads are useless for all but very specialized applications, primarily historical and non-computer. And almost any system that uses a one-time pad is insecure. It will claim to use a one-time pad, but actually use a two-time pad (oops). Or it will claims to use a one-time pad, but actually use a steam cipher. Or it will use a one-time pad, but won't deal with message re-snchronization and re-transmission attacks. Or it will ignore message authentication, and be susceptible to bit-flipping attacks and the like. Or it will fall prey to keystream reuse attacks. Etc., etc., etc. - Though it has a large key length greater than or equal to the plain text,why would it be insecure if we can use a good pseudo random number generators,store the bits produced on a taper proof medium. how about this way P=Plain text C=Cipher text R=Pseudo random bits(the pad) To transmit a secret frm point A to Point B Choose ur agent-Send cipher text(C) to B. If( Cipher text C is intercepted,do not send R.) without R, C cannot be decrypted Else(If C is securely transmitted to point B,choose an agent and send R to point B) If R is intercepted the secret remains safe,since they donot have C. If initially C was intercepted ,R is not send,another pad is chosen. It is assumed that the agent is trust worthy.Also the agent has to send receipt for the safe arrival of C at point B before R is transmitted. It is also assumed that cryptographical secure pseudo random numbers are use. Cryptography does not address the problem of dishonest users-does it? The difficulty for attaining highest security is more. why do we always have to rely on the internet for sending the pad?If it is physically carried to the receiver we can say for sure if P or R is intercepted. can some one answer the issues involved that one time pads is not a good choice. Thank you Regards Sarath. __ Do you Yahoo!? Faith Hill - Exclusive Performances, Videos & More http://faith.yahoo.com
Re: One time pads
Naive question here, but what if you made multiple one time pads (XORing them all together to get your "true key") and then sent the different pads via different mechanisms (one via FedEx, one via secure courier, one via your best friend)? Unless *all* were compromised, the combined key would still be secure. As for PKI being secure for 20,000 years, it sure as hell won't be if those million-qubit prototypes turn out to be worth their salt. Think more like 5-10 years. In fact, just about everything except for OTP solutions will be totally, totally fucked. Which means that you should start thinking about using OTP *now* if you have secrets you'd like to keep past when an adversary of yours might have access to a quantum computer. I'd put 50 years as an upper bound on that, 5 years as a lower. -d - Original Message - From: "David Howe" <[EMAIL PROTECTED]> To: "Email List: Cypherpunks" <[EMAIL PROTECTED]> Sent: Wednesday, October 16, 2002 7:52 AM Subject: Re: One time pads > at Wednesday, October 16, 2002 2:01 PM, Sarad AV > <[EMAIL PROTECTED]> was seen to say: > > Though it has a large key length greater than or equal > > to the plain text,why would it be insecure if we can > > use a good pseudo random number generators,store the > > bits produced on a taper proof medium. > because you have replaced a OTP (provably secure) with a PRNG stream > cypher (only as secure as the PRNG). he isn't saying that stream cyphers > can't be secure - just that they aren't OTP. > There is also no point in distributing the output of a PRNG as a > tamperproof tape - you just run the PRNG at both sides, in sync. > if you use a *real* RNG, then you can do the tape disribution thing and > it *will* be a OTP - but its the tape distribution that is the difficult > bit (as he points out in the article) > > > why do we always have to rely on the internet for > > sending the pad?If it is physically carried to the > > receiver we can say for sure if P or R is intercepted. > two obvious points are > 1. it isn't aways possible to ensure secure delivery - if a courier is > compromised or "falls asleep" and the tape is substituted with another, > a mitm attack can be made transparently. > 2. if the parties are physically remote, they may not have time to > exchange tapes securely; unless there is a airplane link directly or > indirectly between the sites, it may be days or weeks in transit. > > > can some one answer the issues involved that one time > > pads is not a good choice. > OTP is the best choice for something that must be secret for all time, > no matter what the expense. > anything that "secure for 20,000 years" will be sufficient for, go for > PKI instead :)
Re: One time pads
at Wednesday, October 16, 2002 2:01 PM, Sarad AV <[EMAIL PROTECTED]> was seen to say: > Though it has a large key length greater than or equal > to the plain text,why would it be insecure if we can > use a good pseudo random number generators,store the > bits produced on a taper proof medium. because you have replaced a OTP (provably secure) with a PRNG stream cypher (only as secure as the PRNG). he isn't saying that stream cyphers can't be secure - just that they aren't OTP. There is also no point in distributing the output of a PRNG as a tamperproof tape - you just run the PRNG at both sides, in sync. if you use a *real* RNG, then you can do the tape disribution thing and it *will* be a OTP - but its the tape distribution that is the difficult bit (as he points out in the article) > why do we always have to rely on the internet for > sending the pad?If it is physically carried to the > receiver we can say for sure if P or R is intercepted. two obvious points are 1. it isn't aways possible to ensure secure delivery - if a courier is compromised or "falls asleep" and the tape is substituted with another, a mitm attack can be made transparently. 2. if the parties are physically remote, they may not have time to exchange tapes securely; unless there is a airplane link directly or indirectly between the sites, it may be days or weeks in transit. > can some one answer the issues involved that one time > pads is not a good choice. OTP is the best choice for something that must be secret for all time, no matter what the expense. anything that "secure for 20,000 years" will be sufficient for, go for PKI instead :)
Re: One time pads
At 7:52 AM -0700 10/16/02, David Howe wrote: >OTP is the best choice for something that must be secret for all time, >no matter what the expense. >anything that "secure for 20,000 years" will be sufficient for, go for >PKI instead :) OTP is also good when: (1) You can solve the key distribution problem. (2) You need a system with a minimum of technology (e.g. no computers) (3) You need high security. The Solvet spies are a case in point. The only incriminating evidence they had with them was the pad itself. Given the small size of their messages, (they didn't throw Microsoft word files around), their pads could also be physically small. The necessary calculations could be performed with pencil and paper, and the incriminating intermediate results burned. And the system, used correctly, provided high security. Of course, when they started using it as a Two Time Pad, the NSA was able to decode messages as shown by the Verona intercepts. Cheers - Bill - Bill Frantz | The principal effect of| Periwinkle -- Consulting (408)356-8506 | DMCA/SDMI is to prevent| 16345 Englewood Ave. [EMAIL PROTECTED] | fair use. | Los Gatos, CA 95032, USA
RE: One time pads
> David E. Weekly[SMTP:[EMAIL PROTECTED]] > > Naive question here, but what if you made multiple one time pads (XORing > them all together to get your "true key") and then sent the different pads > via different mechanisms (one via FedEx, one via secure courier, one via > your best friend)? Unless *all* were compromised, the combined key would > still be secure. > > As for PKI being secure for 20,000 years, it sure as hell won't be if > those > million-qubit prototypes turn out to be worth their salt. Think more like > 5-10 years. In fact, just about everything except for OTP solutions will > be > totally, totally fucked. Which means that you should start thinking about > using OTP *now* if you have secrets you'd like to keep past when an > adversary of yours might have access to a quantum computer. I'd put 50 > years > as an upper bound on that, 5 years as a lower. > > -d > Not quite right. My understanding is that quantum computing can effectively halve the length of a symmettric key, but that does not take it down to zero. Thus, a 256 bit key would, in a QC world, be as secure as a 128 bit key today, which is to say, pretty good. It's the asymmetric algorithms which have problems. Peter