Re: luks disk encryption benchmarks
On Tue, Jun 05, 2007 at 07:00:51PM -0500, Travis H. wrote: I just did some performance testing on a file server (debian 4.0) and thought I'd share the figures, both raw and using the luks cryptosystem described here: http://luks.endorphin.org/about Here's the specs: AMD Athlon 64 x2 3600+ (1800MHz) 2GB 800MHz DDR2 ECC DRAM Asus M2N32WS motherboard 3ware 9650SE SATA RAID controller (PCI Express) in PCI Express x16 slot 4 Seagate SATA-II 500GB 7200 RPM drives with NCQ in RAID 10 configuration 16kB stripe size Debian 4.0 stable (etch) My hunch is that over NFS, even with gigabit ethernet, there will be no measurable difference between encrypted and non-encrypted storage. raw over NFS: Version 1.03 --Sequential Output-- --Sequential Input- --Random- -Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks-- MachineSize K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP nfsclient4G 16756 61 40475 21 12033 9 15669 85 15564 6 445.8 3 --Sequential Create-- Random Create -Create-- --Read--- -Delete-- -Create-- --Read--- -Delete-- files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP 16 2329 12 8480 32 4185 22 1857 10 9742 27 3692 18 nfsclient,4G,16756,61,40475,21,12033,9,15669,85,15564,6,445.8,3,16,2329,12,8480,32,4185,22,1857,10,9742,27,3692,18 crypt over NFS: Version 1.03 --Sequential Output-- --Sequential Input- --Random- -Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks-- MachineSize K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP nfsclient4G 16416 61 33488 13 10666 9 14084 73 16143 7 392.7 3 --Sequential Create-- Random Create -Create-- --Read--- -Delete-- -Create-- --Read--- -Delete-- files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP 16 2218 12 7444 25 4248 20 2288 12 9401 28 3575 15 nfsclient,4G,16416,61,33488,13,10666,9,14084,73,16143,7,392.7,3,16,2218,12,7444,25,4248,20,2288,12,9401,28,3575,15 So... yeah, pretty minimal - IMHO, not worth worrying about. -- ``To know love, be like the running brook, which though deaf, sings its melody for others to hear.'' -- Master Po, Kung Fu URL:http://www.subspacefield.org/~travis/ -- dharma advaita For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgp0t6UIV8S0K.pgp Description: PGP signature
luks disk encryption benchmarks
I just did some performance testing on a file server (debian 4.0) and thought I'd share the figures, both raw and using the luks cryptosystem described here: http://luks.endorphin.org/about Here's the specs: AMD Athlon 64 x2 3600+ (1800MHz) 2GB 800MHz DDR2 ECC DRAM Asus M2N32WS motherboard 3ware 9650SE SATA RAID controller (PCI Express) in PCI Express x16 slot 4 Seagate SATA-II 500GB 7200 RPM drives with NCQ in RAID 10 configuration 16kB stripe size Debian 4.0 stable (etch) # time dd if=/dev/zero of=/dev/sdb bs=1024k count=1000 1000+0 records in 1000+0 records out 1048576000 bytes (1.0 GB) copied, 23.0923 seconds, 45.4 MB/s real0m23.094s user0m0.000s sys 0m4.508s Now here demonstrates the luks cryptsetup overhead: # time dd if=/dev/zero of=/dev/mapper/bulk bs=1024k count=1000 1000+0 records in 1000+0 records out 1048576000 bytes (1.0 GB) copied, 31.0872 seconds, 33.7 MB/s real0m31.089s user0m0.004s sys 0m14.053s So, with write-caching disabled, performance is fairly close. Then I enabled write-caching and got this: # time dd if=/dev/zero of=/dev/sdb bs=1024k count=1000 1000+0 records in 1000+0 records out 1048576000 bytes (1.0 GB) copied, 3.08291 seconds, 340 MB/s real0m3.126s user0m0.000s sys 0m1.996s That seems to reflect that it isn't really going to disk. I'm surprised the controller has that much RAM on it, really... so I ran this: # time dd if=/dev/zero of=/dev/sdb bs=1024k count=4000 4000+0 records in 4000+0 records out 4194304000 bytes (4.2 GB) copied, 81.0223 seconds, 51.8 MB/s real1m21.024s user0m0.004s sys 0m19.197s Now here's the overhead with encryption: # time dd if=/dev/zero of=/dev/mapper/bulk bs=1024k count=4000 4000+0 records in 4000+0 records out 4194304000 bytes (4.2 GB) copied, 151.202 seconds, 27.7 MB/s real2m31.227s user0m0.008s sys 1m29.318s Based on this, it looks like one of two things is happening: Write cache is 2GB and encryption cancels it out OR Encryption reduces bandwidth by about a factor of 2 with write-caching enabled. Now, for these filesystem tests I just used the default ext3... it does use a journal, which will slow down writes, but this should give ballpark figures: Here are the filesystem-level benchmarks without encryption (using LVM to make the filesystem 4G or so): Version 1.03 --Sequential Output-- --Sequential Input- --Random- -Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks-- MachineSize K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP machine4G 54305 96 84213 14 37749 8 52767 94 119217 13 436.6 0 --Sequential Create-- Random Create -Create-- --Read--- -Delete-- -Create-- --Read--- -Delete-- files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP 16 5175 99 + +++ + +++ 5131 99 + +++ 14419 99 machine,4G,54305,96,84213,14,37749,8,52767,94,119217,13,436.6,0,16,5175,99,+,+++,+,+++,5131,99,+,+++,14419,99 Here's the filesystem-level performance with encryption (again, with LVM on top of the encryption, file system 10G): Version 1.03 --Sequential Output-- --Sequential Input- --Random- -Per Chr- --Block-- -Rewrite- -Per Chr- --Block-- --Seeks-- MachineSize K/sec %CP K/sec %CP K/sec %CP K/sec %CP K/sec %CP /sec %CP machine4G 36692 98 79380 71 28544 6 50631 91 74157 9 464.5 0 --Sequential Create-- Random Create -Create-- --Read--- -Delete-- -Create-- --Read--- -Delete-- files /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP /sec %CP 16 5344 99 + +++ + +++ 5261 99 + +++ 16060 99 machine,4G,36692,98,79380,71,28544,6,50631,91,74157,9,464.5,0,16,5344,99,+,+++,+,+++,5261,99,+,+++,16060,99 This presents a more interesting picture; it appears that for work on actual files, the overhead is pretty modest... with all but character-at-a-time input, it's not worth worrying about. My hunch is that over NFS, even with gigabit ethernet, there will be no measurable difference between encrypted and non-encrypted storage. -- ``To know love, be like the running brook, which though deaf, sings its melody for others to hear.'' -- Master Po, Kung Fu URL:http://www.subspacefield.org/~travis/ -- For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpHe5SIlTgbj.pgp Description: PGP signature
crypto maxims
I have posted my ideas on defensive use of crypto here: https://www.subspacefield.org/security/cgi-bin/moin.py/CryptoMaxims This is not about cipher design, it's more about protocol design and implementation. Everyone here is welcome to edit it as they see fit; questions and answers, discussion - the goal is education, so all of those are desirable. -- Good idea: helping a stranger move Bad idea: helping a stranger move bodies URL:http://www.subspacefield.org/~travis/ -- For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpxaOXrYkI6v.pgp Description: PGP signature
kernel-level key management subsystem
Ignoring special-purpose hardware, does anyone have thoughts on what the requirements for a kernel-level key management subsystem should be? -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgp9WQGxTEqLS.pgp Description: PGP signature
Re: More info in my AES128-CBC question
On Wed, May 09, 2007 at 06:11:03PM -0400, Leichter, Jerry wrote: Just being able to generate traffic over the link isn't enough to carry out this attack. Well, it depends on if you key per-flow or just once for the link. If the latter, and you have the ability to create traffic over the link, and there's a 1-for-1 correspondence between plaintext and encrypted packets, then you have a problem. Scenarios include: Private wifi network, you are sending packets at a customer from unprivileged node on internet; you want known plaintext for the key used to secure the wifi traffic, or you want the contents of his connection. Target is VPN'ed into corporate headquarters, you are sending packets at them (or you send them email, they download it from their mail server) -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpEWNibI30LX.pgp Description: PGP signature
Re: phone encryption technology becoming popular in Italy
On Wed, May 02, 2007 at 06:12:31PM +0100, Dave Korn wrote: If you wanted to be /really/ certain, I guess you'd have to take the tops off all the ICs inside and look at them under an EM, to make sure they really were the parts they claimed to be and don't have any extra circuitry or hidden functions built in If the chips had more than a single layer, or even if they were single layer, it's probably possible to hide some functionality. I've heard of devices that are capable of displaying the current flowing through the conductive regions of the chip (electrons move just a little too fast to follow, about 1/4 the speed of light in copper) but that's an awfully labor-intensive way to check that everything is working to spec... it's probably cheaper to build it yourself. And then with respect to the non-crypto issues; are you going to cut open every capacitor on the red signal path to check for, say, miniature FM transmitters? I'm reminded a bit of the US embassy in Moscow, where (using neutron scanners) they found bugs in the girders that were the same density as the steel, and so invisible to X-rays... in the end, they learned that the only way to avoid these kinds of surprises was to use only their own building materials and labor. Earlier in this list tamper-resistant hardware was mentioned... the downside of that is that unless you're the manufacturer, your attempts to verify that it doesn't have any surprises look a whole lot like the kind of tampering it is designed to resist... It seems like this is a deep rabbit hole with no obvious end. Probably the best one could hope for is to avoid targeted attacks, where the opponent knows you are getting something and has it customized for you. Widespread (indiscriminate) compromisation is probably impractical to detect. If you're a nation, or particularly wealthy, then perhaps you can do it all yourself, but for high-tech devices that can get very expensive. History is littered with examples where countries tried to create a domestic source for some strategic good and failed miserably. Incidentally, on my web page I have some pictures and code for a HWRNG that an associate built (I wrote the software); he made a limited run of 10 or so, but if anyone wants the schematics, you'll want to send a SASE to Brad Martin at http://www.nshore.com/ (the plans are not in an easy-to-email form and this method filters out all but serious inquiries). It is actually a pretty neat device, battery powered to avoid 60Hz signal injection (you can use a wall wart if you want to though, the filters are good) and even enters a power-saving mode when not in use. My software (written for Linux and BSD) supports a mode where it allows the device to power down when /dev/random is above a high water mark, and automatically powers it up when it drops below it. One person called it the most over-engineered RNG I have ever seen. I think the cost to build one is about $100-200, but Brad spent $30k of unbillable time on this personal project, mostly on the design. It's a shame to see that only used on 10 units. There are, incidentally, some open-source hardware web sites, where they have schematics for various chips and cores... although you can't just etch your own silicon, there are shops that do all of that for you; you just email them the layouts and send them the money, and they can do a small run of chips for reasonable prices. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpBE4zRtMeSN.pgp Description: PGP signature
Re: More info in my AES128-CBC question
On Wed, May 09, 2007 at 06:04:20PM -0400, Leichter, Jerry wrote: However, cryptographically secure RNG's are typically just as expensive as doing a block encryption. So why not just encrypt the IV once with the session key before using it? (This is the equivalent of pre-pending a block of all 0's to each packet.) There's many ways to deal with it if you're willing to do more crypts per block. For example, you could derive an independent key and use that to encrypt a counter for IVs... becoming a cryptographically strong permutation... that'd work as long as you didn't send so many IVs that you ran through most of the cycle (the last value in the cycle is 100% predictable). -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpYqqeHkErOq.pgp Description: PGP signature
Re: More info in my AES128-CBC question
On Fri, Apr 27, 2007 at 05:13:44PM -0400, Leichter, Jerry wrote: Frankly, for SSH this isn't a very plausible attack, since it's not clear how you could force chosen plaintext into an SSH session between messages. A later paper suggested that SSL is more vulnerable: A browser plugin can insert data into an SSL protected session, so might be able to cause information to leak. Hmm, what about IPSec? Aren't most of the cipher suites used there CBC mode? If it doesn't key each flow seperately, and the opponent has the ability to generate traffic over the link, which isn't unreasonable, then this would seem feasible. And then there's openvpn, which uses SSL for the point-to-point link, thus probably vulnerable, more vulnerable than a browser. I am also aware of SSL being used many places other than browsers and openvpn. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpvjZwMdNcnK.pgp Description: PGP signature
Re: Public key encrypt-then-sign or sign-then-encrypt?
On Wed, May 02, 2007 at 09:29:39AM -0600, Anne Lynn Wheeler wrote: where there is possibly the suggestion that if the only thing being performed is authentication (and doesn't require either integrity and/or privacy) ... then possibly a totally different protocol by utilized (rather than digital signature) This reminds me a bit of a suggestion I once heard for protocol designers that the messages of the various steps of the protocol include a step number or something like it to prevent cut-and-paste attacks (presumably each message has some redundancy to protect the integrity/authenticity as well, like a running hash covering all the previous messages (in this direction)). I wonder if something similar couldn't be done with digital signatures, where the input is padded with data that indicates the semantics of the signature; not unlike the forms which say by signing here I agree that... This also makes it very difficult for the opponent to do any kind of chosen-plaintext trickery since the plaintext will be framed with this data that the opponent does not control, but that is also true with other padding options and such. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpnvBUihZ9Sw.pgp Description: PGP signature
Re: Public key encrypt-then-sign or sign-then-encrypt?
On Thu, May 03, 2007 at 07:57:18PM +1000, James A. Donald wrote: Assume Ann's secret key is a, and her public key is A = G^a mod P Assume Bob's secret key is b, and his public key is B = G^b mod P Bob wants to send Ann a message. Bob generates a secret random number x, and sends Ann X = G^x mod P Ann responds with Y = G^y mod P, where y is another secret random number. Ann calculates [(B*X)^(a+y)] mod P This appears to simplify to: (G^b * G^x)^(a+y) = (G^(b+x))^(a+y) = G^((b+x)(a+y)) Right? This doesn't appear to be anything like the latest rev of the OTR protocol: http://www.cypherpunks.ca/otr/Protocol-v2-3.0.0.html Apparently they key exchange is now a variant of the SIGMA protocol, and relies upon the implementation to disclose MAC keys automagically as the related session keys are destroyed/expired. Apparently this fixes an identity-binding flaw: http://lists.cypherpunks.ca/pipermail/otr-users/2005-July/000316.html And this illustrates a subtlety: For example, if Bob thinks he's talking to Mallory, he may tell her something in confidence he would not want Alice to hear. Note that although Mallory could relate this confidential information to Alice herself, but in the attack scenario Alice has assurance that the message came from Bob rather than having to take Mallory's word for it. Contrast this to sign-then-encrypt, where Mallory could decrypt, then forward to Alice. Compare with encrypt-then-sign. But it brings up an interesting point; that when a party relays a piece of data it may not be equivalent to receiving it directly; that is, authenticity may not be transitive. Put another way, maybe it's not the information that matters, but who says it. The New York Times may say that someone did XYZ, but that's not entirely the same as the person admitting it under oath. In international politics, many believe that admitting to having performed some provocative action can be more provocative than actually the action itself, even if everyone already knows who is responsible. If you believe this, I suppose the official lie can be said to serve the interest of both sides, as the government receiving the provocation can allow the story to go unchallenged, and probably not be forced into taking an overt retaliatory action. Thus it preserves their options, and avoids forcing them into what could be a disastrous confrontation. If they are too weak to confront the provocateur, they aren't likely to shout this from the rooftops. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgp2OKJBtiEKs.pgp Description: PGP signature
Re: More info in my AES128-CBC question
On Wed, Apr 25, 2007 at 05:42:44PM -0500, Nicolas Williams wrote: A confounder is an extra block of random plaintext that is prepended to a message prior to encryption with a block cipher in CBC (or CTS) mode; the resulting extra block of ciphertext must also be sent to the peer. Not true. Since we are comparing confounders to IVs, let's make identical assumptions; that the value is somehow agreed upon in advance. Then, one need not send it; the receiver can compute C_(i-1) = E_k(confounder) without actually having it sent to him, and from there continue decryption with P_i = C_(i-1) xor D_k(C_i) and so on. If the IV chained across continguous messages as in SSHv2 then you have a problem (see above). I don't fully understand what it means to have IVs chained across contiguous (?) messages, as in CBC mode each ciphertext block forms the IV of the block after it, effectively; basically an IV is just C_0 for some stream. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgp5R1OqVH44H.pgp Description: PGP signature
Why CBC? What is wrong with n-bit CFB?
I've always wondered this about the lesser-used modes. What's special about CBC? With CFB in particular, I think 8-bit CFB is stupid (one full block encryption per byte processed - rather computationally expensive), but n-bit CFB seems just as useful as CBC, if not more so. Specifically, I can start sendings bits of C_(i-1) = IV xor P_(i-1) as soon as I feel like it, even before all of P_(i-1) is in, and it uses the same number or less crypts than CBC. Futhermore, it can be used to encrypt in place like CBC but without any special ciphertext stealing or other processing. Of course I assume that integrity is handled by a completely seperate mechanism that includes redundancy; anything less is snake oil. For that matter, error extension doesn't seem to be an issue to me in most cases. Error handling should be done via a seperate layer that adds redundancy to the ciphertext prior to transmission (and can do error correction, not just detection). If any error is so bad that it defeats this layer, I want to know about it (and will find out via yet another layer, an integrity/authenticity layer); it could also be a malicious attack, and unless there is bad sunspot or EMP activity the seperation of duties allows me to distinguish between the two. The exception I can see is if retransmission or delay is unacceptable and it is better to get a garbled message than none at all. This may be the case with human spies in occupied territory, or perhaps for emergency messages to a deep space probe, or such. Still, this is the Internet age and transmission errors are increasingly handled by the lower layers. Is anyone actually doing crypto with plaintext that is interpreted by humans (so they can detect and deal with garbles) over radio any more? Not many among us here I suspect. That having been said, I can't see much in favor of OFB over CTR mode. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpVkl00SrKY3.pgp Description: PGP signature
truncating MACs for confidentiality, was Re: Public key encrypt-then-sign or sign-then-encrypt?
One more thing to consider; if you pick a reasonable MAC with twice the security factor you need, then truncate the output to half the size, I believe you get both confidentiality and integrity/authentication guarantees of the desired strength. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpmO9O0IvaLW.pgp Description: PGP signature
open source disk crypto update
Forgive me as this isn't as technical as the usual posts, but I find it interesting nonetheless. OpenBSD has, for some time, supported encrypted swap. Just recently I discovered Debian default installs now support encrypted root (/boot still needs to be decrypted). Presumably we are moving back the end of the attack surface; with encrypted root, one must attack /boot or the BIOS. What is the limit? I think a simple evolution would be to make /boot and/or /root on removable media (e.g. CD-ROM or USB drive) so that one could take it with you. Of course if someone reflashes your BIOS you are still hosed, but it appears that there's no way to completely eliminate that kind of threat without taking the whole system with you. -- Kill dash nine, and its no more CPU time, kill dash nine, and that process is mine. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpUUuyAM5f8F.pgp Description: PGP signature
Re: interesting and thought provoking resources on quantum crypto
On Thu, Feb 08, 2007 at 04:29:25PM -0800, Saqib Ali wrote: i have been tasked by my advisor to create series of mini-lectures slides on the topic of cryptography for a freshman year CS class. You know, you shouldn't use the Internet to ask people to do your homework for you... ;-) j/k any thoughts? the resource has to be related to quantum crypto... Well, this company sells quantum cryptography devices: http://www.idquantique.com/home.htm On the other side, any link collection on quantum _cryptanalysis_ wouldn't be complete without Shor: http://www-math.mit.edu/~shor/ I went to one of his lectures at my university, and it was one of those experiences where you know they're speaking English, but it's just not communicating information to you. Usually this means one of two things; either they are trying to fool you, or you are the fool. I'm convinced it was the latter. I know an EPR pair from a quantum decoy, but I still have no idea what the angles on his graphs had to do with QC and superposition. Lots of good papers on his electronic publications list: http://www-math.mit.edu/~shor/elecpubs.html He points to this wiki: http://www.qubit.org/ This page is about the watershed paper: http://en.wikipedia.org/wiki/Shor's_algorithm And this page attempts to illustrate it: http://pdivos.mobstop.com/shor/ -- Good code works. Great code can't fail. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpS1PBD0MH5l.pgp Description: PGP signature
Re: Entropy of other languages
On Sun, Feb 04, 2007 at 03:46:41PM -0800, Allen wrote: An idle question. English has a relatively low entropy as a language. Don't recall the exact figure, but if you look at words that start with q it is very low indeed. I seem to recall Shannon did some experiments which showed that with a human as your probability oracle, it's roughly 1-2 bits per letter. Many of his papers are online last time I looked, but some of his experimental results are harder to locate online. What about other languages? Does anyone know the relative entropy of other alphabetic languages? What about the entropy of ideographic languages? Pictographic? Hieroglyphic? IIRC, it turned out that Egyptian heiroglyphs were actually syllabic, like Mesopotamian, so no fun there. Mayan, on the other hand, remains an enigma. I read not long ago that they also had a way of recording stories on bundles of knotted string, like the end of a mop. -- The driving force behind innovation is sublimation. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpyE3iyc6JFI.pgp Description: PGP signature
Re: Entropy of other languages
On Wed, Feb 07, 2007 at 05:42:49AM -0800, Sandy Harris wrote: He starts from information theory and an assumption that there needs to be some constant upper bound on the receiver's per-symbol processing time. From there, with nothing else, he gets to a proof that the optimal frequency distribution of symbols is always some member of a parameterized set of curves. Do you remember how he got from the upper bound on processing time to anything other than a completely uniform distribution of symbols? Seems to me a flat distribution has the minimal upper bound on information content per symbol for a given amount of information! -- Good code works. Great code can't fail. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpmipxzIhxBi.pgp Description: PGP signature
Re: Entropy of other languages
On Wed, Feb 07, 2007 at 05:53:16PM -0500, Steven M. Bellovin wrote: Speakers of such Native American languages as Navajo, Choctaw and Cheyenne served as radio operators, know as Code Talkers, to keep communications secret during both World Wars. Welsh speakers played a similar role during the Bosnian War. Does anyone know anything more about this use of Welsh? http://en.wikipedia.org/wiki/Welsh_Guards says: In 2002 the regiment arrived in Bosnia as part of SFOR, a NATO-led force intended to ensure peace and stability reigns supreme in the Balkan nation. During their deployment HM the Queen Mother died. A number of officers of the Welsh Guards stood in vigil around the Queen Mother's coffin which was lying in state in Westminster Hall, one of a number of regiments to do so. The regiment returned home from their deployment to Bosnia later in the year. That's all I could find in a 10 minute search... -- Good code works. Great code can't fail. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgp0PTSZawU9U.pgp Description: PGP signature
OTP, was Re: data under one key, was Re: analysis and implementation of LRW
On Sun, Feb 04, 2007 at 11:27:00PM -0500, Leichter, Jerry wrote: | 1) use a random key as large as the plaintext (one-time-pad) ...thus illustrating once again both the allure and the uselessness (in almost all situations) of one-time pads. For long-term storage, you are correct, OTP at best gives you secret splitting. However, if people can get at your stored data, you have an insider or poor security (network or OS). Either way, this is not necessarily a crypto problem. The system should use conventional crypto to deal with the data remanance problem, but others have alleged this is bad or unnecessary or both; I haven't seen it proven either way. In any case, keeping the opponent off your systems is less of a crypto problem than a simple access control problem. It was my inference that this data must be transmitted around via some not-very-secure channels, and so the link could be primed by exchanging key material via registered mail, courier, or whatever method they felt comfortable with for communicating paper documents _now_, or whatever system they would use with key material in any other proposed system. The advantage isn't magical so much as practical; you don't have to transmit the pad material every time you wish to send a message. You do have to store it securely (see above). You should compose it with a conventional system, for the best of both worlds. Of course any system can be used incorrectly; disclosing a key or choosing a bad one can break security in most systems. So you already have a requirement for unpredictability and secure storage and confidential transmission of key material (in the case of symmetric crypto). The OTP is the only cipher I know of that hasn't had any cryptanalytic success against it for over 70 years, and offers a proof. [1] As an aside, it would be interesting to compare data capacity/density and networking speeds to see if it is getting harder or easier to use OTP to secure a network link. [1] Cipher meaning discrete symbol-to-symbol encoding. OTP's proof does rely on a good RNG. I am fully aware that unpredictability is just as slippery a topic as resistance to cryptanalysis, both being universal statements that can only be proved by a counterexample, but that is an engineering or philosophical problem. By securely combining it with a CSPRNG you get the least predictable of the pair. Everyone in reliable computing understands that you don't want single points of failure. If someone proposed that they were going to deploy a system - any system - that could stay up for 70 years, and it didn't have any form of backup or redundancy, and no proof that it wouldn't wear down over 70 years (e.g. it has moving parts, transistors, etc.), they'd be ridiculed. And yet every time OTP comes up among cryptographers, the opposite happens. When it comes to analysis, absence of evidence is not evidence of absence. Anyway ... while the question how can we keep information secure for 70 years has some theoretical interest, we have enough trouble knowing how to keep digital information *accessible* for even 20 years that it's hard to know where to reasonably start. I think that any long-term data storage solution would have to accept two things: 1) The shelf life is a complete unknown. By the time we know it, we will be using different media, so don't hold your breath. 2) The best way to assure being able to read the data is to seal up a seperate instance of the hardware, and to use documented formats so you know how to interpret them. Use some redundancy, too, with tolerance of the kind of errors the media is expected to see. 3) Institutionalize a data refresh policy; have a procedure for reading the old data off old media, correcting errors, and writing it to new media (see below). The trend seems to be that I/O capacity is going up much faster than I/O bandwidth is increasing, and there doesn't seem to be a fundamental limitation in the near future, so the data is cooling rapidly and will continue to do so (in storage jargon, temperature is related to how often the data is read or written). Further, tape is virtually dead, and it looks like disk-to-disk is the most pragmatic replacement. That actually simplifies things; you can migrate the data off disks before they near their lifespan in an automated way (plug in new computer, transfer data over direct network connection, drink coffee). Or even more simply, stagger your primary and backup storage machines, so that 1/2 way through the MTTF of the drive, you have a new machine with a new set of drives as the backup, do one backup and swap roles. Now your data refresh and backup are handled with the same mechanism. At least, that's what I'm doing. YMMV. -- The driving force behind innovation is sublimation. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgp876Gxt2EB4.pgp Description: PGP signature
deriving multiple keys from one passphrase
Hey, quick question. If one wants to have multiple keys, but for ease-of-use considerations want to only have the user enter one, is there a preferred way to derive multiple keys that, while not independent, are computationally independent? I was thinking of hashing the passphrase with a unique string for each one; is this sufficient? If sufficient, is a cryptographically strong hash necessary? I got a clarification about the use CRCs to process passphrase idea someone mentioned. The salient bit is that he was using several CRCs (not sure if it's random or carefully chosen), and each one is run on the passphrase, and the output of all of them concatenated to initialize a PRNG seed. The passphrase and seed are both secret, so according to him there's no need to use a cryptographically strong hash, and CRCs have a well-understood mathematical basis. I presume this would be insufficient for deriving independent keys, but perhaps there is a way to do that with careful selection of the CRC polys? -- The driving force behind innovation is sublimation. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpgxzMEc4EYQ.pgp Description: PGP signature
data under one key, was Re: analysis and implementation of LRW
On Wed, Jan 24, 2007 at 03:28:50PM -0800, Allen wrote: If 4 gigs is right, would it then be records to look for to break the code via birthday attacks would be things like seismic data, In case anyone else couldn't parse this, he means the amount of encrypted material necessary to break the key would be large or the size of a lookup table would be large or something like that. Currently I'm dealing with very large - though not as large as 4 gig - x-ray, MRI, and similar files that have to be protected for the lifespan of the person, which could be 70+ years after the medical record is created. Think of the MRI of a kid to scan for some condition that may be genetic in origin and has to be monitored and compared with more recent results their whole life. That's longer than computers have been available, and also longer than modern cryptography has existed. The only way I would propose to be able to stay secure that long is either: 1) use a random key as large as the plaintext (one-time-pad) 2) prevent the ciphertext from leaking (quantum crypto, spread-spectrum communication, steganography) Even then, I doubt Lloyd's would insure it. Anyone who claims to know what the state of the art will be like in 70+ years is a fool. I would be cautious about extrapolating more than five years. The problem is not the amount of data under one key; that's easy enough, generate random keys for every n bits of plaintext and encrypt them with a meta-key, creating a two-level hierarchy. You calculate a information-theoretic bound on n by computing the entropy of the plaintext and the unicity distance of the cipher. Note that the data (keys) encrypted directly with the meta-key is completely random, so the unicity distance is infinite. Furthermore, one can't easily brute-force the meta-key by trying the decrypted normal keys on the ciphertext because all the plaintext under one key equivocates because it is smaller than the unicity distance. I'm not sure how it compounds when the meta-key encrypts multiple keys, I'd have to look into that. In any case, you can create a deeper and deeper hierarchy as you go along. This bound is the limit for information-theoretic, or unconditional security. Shannon proved that a system with these characteristics is unbreakable. If you don't know what the entropy of the plaintext is, you have to use a one-time pad. The unicity distance of DES, last time I looked, was so low that one might as well use a one-time pad. With computational security, you can fudge a little by trying to calculate how much data you can safely encrypt under one key. However, I believe this value can only go down over time, as new cryptanalytic attacks are developed against the cipher. Another method is to derive many data keys from bits of a larger meta-key in a way that is computationally infeasible. However, every time you hear computationally infeasible, remember that it is an argument of ignorance; we don't know an efficient way to break it, yet, or if someone does they aren't talking. You can also make this argument more scientific by extrapolating future attacks and computational advances from trends (Moore's Law et. al.) - see Rules of Thumb in Data Engineering from Microsoft; it's on the storagemojo.com blog and well worth reading. Furthermore, you should provide a mechanism for the crypto to be changed transparently as technology progresses; an installed base is forever, but computational security is not. Permitting multiple security configurations is complex, but I don't think anything short of OTP can give an absolute assurance of confidentiality when the opponent has access to the plaintext. Another simple solution, the belt-and-suspenders method, is to superencrypt the ciphertext with a structurally different cipher. This basically makes the plaintext fed to the top-level cipher computationally indistinguishable from random data, and so the unicity distance of the top-level cipher is infinite according to computational security of the lower-level cipher. I'm mixing terminology here, but the net result is that you're guaranteed that the combination is as secure as either alone, and in most cases a weakness in one cipher will not be a weakness in the other (this is because of the structurally independent assumption). You get the same effect by sending an encrypted file over an encrypted network connection (unless the file is converted to base64 or something prior to transmission), assuming that the opponent is not an insider with access to decrypted network traffic. Some assumptions to consider are: What problem(s) are we trying to solve, and why? Can we set up a secure distribution network for key material? Who is the opponent? How many years will they remain interested in a captured record? What is the budget? Who are the users? How competent are they? How much can we educate them? How will we fix bugs or update it? What are the security priorities?
length-extension and Merkle-Damgard hashes
So I was reading this: http://en.wikipedia.org/wiki/Merkle-Damgard It seems to me the length-extension attack (given one collision, it's easy to create others) is not the only one, though it's obviously a big concern to those who rely on it. This attack thanks to Schneier: If the ideal hash function is a random mapping, Merkle-Damgard hashes which don't use a finalization function have the following property: If h(m0||m1||...mk) = H, then h(m0||m1||...mk||x) = h(H||x) where the elements of m are the same size as the block size of the hash, and x is an arbitrary string. Note that encoding the length at the end permits an attack for some x, but I think this is difficult or impossible if the length is prepended. -- The driving force behind innovation is sublimation. -- URL:http://www.subspacefield.org/~travis/ For a good time on my UBE blacklist, email [EMAIL PROTECTED] pgpL5KPdwlGvf.pgp Description: PGP signature
block cipher modes and collisions
The wikipedia page on the IEEE SISWG debate about LRW says: [A] general security requirement for any block cipher, regardless of mode of operation, is that no block cipher should be used to encrypt any more data, without changing the key, when the probability of a collision becomes not negligible (see also birthday paradox). They must mean output collisions, rather than multiple preimages, but I think some modes will have collisions at a rate which depends on the plaintext (LRW being the obvious example)... but I've never heard of this security requirement before. Excepting the Handbook of Applied Cryptography, which I need to read, does anyone have another reference for this requirement, or others like it? I suppose that NIST might have published something like that in the various publications about block cipher modes, but don't know where to look exactly... -- ``Unthinking respect for authority is the greatest enemy of truth.'' -- Albert Einstein -- URL:http://www.subspacefield.org/~travis/ pgp39knc2U9V2.pgp Description: PGP signature
OT: SSL certificate chain problems
Hi, This is not really typical of the traffic on this list, hence the OT. I send it because I think this is one of the few places where I'll find some people with deep understanding of SSL certs. Recently I had an issue where Google checkout would not accept an SSL certificate because Apache didn't present the entire hierarchy, just the site certificate itself. The CA was Thawte. What Google said was that many browsers supply missing certs as needed, but apparently their software did not. The fix would seem to be easy; just put the right CA root cert in the SSLCACertFile directive. or point to the directory with SSLCACertPath. However, I've tried over and over with various root CA certs downloaded from Thawte, and with one intermediate CA cert, and various combinations thereof, but with no sucess. The troubleshooting command line Google gave us was: openssl s_client -connect www.domain.com:443 -showcerts /dev/null Hi, This is not really typical of the traffic on this list, hence the OT. I send it because I think this is one of the few places where I'll find some people with deep understanding of SSL certs. Recently I had an issue where Google checkout would not accept an SSL certificate because Apache didn't present the entire hierarchy, just the site certificate itself. The CA was Thawte. What Google said was that many browsers supply missing certs as needed, but apparently their software did not. The fix would seem to be easy; just put the right CA root cert in the SSLCACertFile directive. or point to the directory with SSLCACertPath. However, I've tried over and over with various root CA certs downloaded from Thawte, and with one intermediate CA cert, and various combinations thereof, but with no sucess. The troubleshooting command line Google gave us was: openssl s_client -connect www.domain.com:443 -showcerts /dev/null Which shows: depth=0 /C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, LLC/CN=www.domain.com verify error:num=20:unable to get local issuer certificate verify return:1 depth=0 /C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, LLC/CN=www.domain.com verify error:num=27:certificate not trusted verify return:1 depth=0 /C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, LLC/CN=www.domain.com verify error:num=21:unable to verify the first certificate verify return:1 CONNECTED(0003) --- Certificate chain 0 s:/C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, LLC/CN=www.domain.com i:/C=ZA/O=Thawte Consulting (Pty) Ltd./CN=Thawte SGC CA -BEGIN CERTIFICATE- [...] -END CERTIFICATE- --- Server certificate subject=/C=US/ST=California/L=Los Angeles/O=Company, LLC/OU=COMPANY, LLC/CN=www.domain.com issuer=/C=ZA/O=Thawte Consulting (Pty) Ltd./CN=Thawte SGC CA --- No client certificate CA names sent --- SSL handshake has read 1396 bytes and written 340 bytes --- New, TLSv1/SSLv3, Cipher is DHE-RSA-AES256-SHA Server public key is 1024 bit Compression: NONE Expansion: NONE SSL-Session: Protocol : TLSv1 Cipher: DHE-RSA-AES256-SHA Session-ID: 0DD3301C8B8AF7BD3706A991475B22580AA32FCF85A141D753E2F051A691ED86 Session-ID-ctx: Master-Key: ... Key-Arg : None Start Time: 1169584627 Timeout : 300 (sec) Verify return code: 21 (unable to verify the first certificate) --- DONE I can't seem to get that certificate chain to have any contents other than what you see above, no matter what I do, and hence can't get rid of the Verify return code: 21... does anyone have any advice on what to do next? URLs or references to other mailing lists welcome. -- ``Unthinking respect for authority is the greatest enemy of truth.'' -- Albert Einstein -- URL:http://www.subspacefield.org/~travis/ pgpOnPmmhdFCX.pgp Description: PGP signature
Re: Private Key Generation from Passwords/phrases
On Sun, Jan 21, 2007 at 12:13:09AM -0500, Steven M. Bellovin wrote: Could you explain this? It's late, but this makes no sense at all to me. I probably wasn't clear, you bring out my realization that there are a number of unwritten assumptions going on here. Similarly, the size of the output is irrelevant; we're not talking about cryptanalysis here. Well, I can't disagree, since I also approved of truncating it to its original size, but I wouldn't want to induce collisions by making the salted input space much larger than the output space, or else the work factor goes down for the attacker, right? that's not the only form of dictionary attack -- see M. Bishop, ?An Application of a Fast Data Encryption Standard Implementation,? Computing Systems 1(3) pp. 221?254 (Summer 1988), for example. I'll have to look at that. With 4K possible salts, you'd need a very large password file to have more than a very few collisions, though. It's only a benefit if the password file (or collection of password files) is very large. Well, birthday paradox here, but what you say is true. IIRC, standard cracker practice back when tftp'ing password files was popular was to pool them all and sort by salt, then computing the most common salts and the most common passwords. There is also some benefit if the attacker is precomputing dictionaries, but there the size of the search space is large enough that the salt factor isn't that important given even minimal quality checks. Really? What about rainbow tables? I heard recently that there was a relatively complete MD5 rainbow table online with an ajax/js interface for searching it. Unless I'm missing something obvious, this basically eliminates the advantage of hashing unsalted passwords with MD5 to null. I look favorably on the formats that allow you to iterate a OWF over the password N times, and that store N in the entry. That way, if the costs of running the algorithm go down, you can just increase the number of times it has been run on every entry in the file without requiring any interaction from end-users. This kind of scaling with the world is needed, because cryptanalysis isn't a stagnant field, and Moore's Law still holds, and I find the idea of having to change between incompatible systems just to keep the same level of security, and on someone else's schedule, to be undesirable. -- ``Unthinking respect for authority is the greatest enemy of truth.'' -- Albert Einstein -- URL:http://www.subspacefield.org/~travis/ pgpI8slDM82ce.pgp Description: PGP signature
Re: Private Key Generation from Passwords/phrases
On Fri, Jan 19, 2007 at 12:11:40AM -0800, Bill Stewart wrote: One of the roots of the problem is that for many applications, i is a well-defined event and P(i) is a fixed value (for i) , but for many other applications, i might not be a well-defined event, and/or P(i) is really a conditional probability, P(i|other-stuff-you-know), and it's hard to tell whether that's usefully different from the non-conditional P(i). Yes; in textbooks, the author is usually kind enough to give a complete description of the source; in cryptanalysis, you're usually looking at the output and making inferences about the source, and thus, the entropy. Another entropy example was the Venona decryptions - people banging randomly on typewriters didn't actually produce independent or identically distributed letters, so the conditional probabilities didn't actually match the assumed ones, so the entropy estimates were wrong, and human language plaintext being what it is, they really needed the 1-bit-per-bit of key entropy. Actually, my reading of a book on Venona said they captured some unused OTP on microfilm, but weren't able to use the non-randomness of the source to decrypt anything. Someone here mentioned that the entropy of the plaintext and the OTP have to merely add to 1 to prevent decryption; the OTP does not necessarily have to provide it all. Shannon's estimates were that English prose carries about 1 bit per symbol. There were some decrypts of material; the official explanation is that they recovered a partial codebook and discovered some OTP re-use (the KGB encoded then superenciphered it). BTW, dictionary attacks can probably be effectively resisted by making the hashes of passwords twice as big, and using a random value concatenated with the password before hashing, and storing it alongside the hash (it's like crypt(3) salting, but more so). If the password is important to keep from disclosure beyond the needs of this security system, one could even truncate the output of the hash to half its size, so that there's multiple preimages; since you doubled the hash size to begin with, you end up with the same security factor against guessing, I believe. -- ``Unthinking respect for authority is the greatest enemy of truth.'' -- Albert Einstein -- URL:http://www.subspacefield.org/~travis/ pgpJoxUCemN6j.pgp Description: PGP signature
Re: gang uses crypto to hide identity theft databases
On Sun, Dec 24, 2006 at 11:10:40PM +, Rick van Rein wrote: This is not =entirely= true. A key stored in the same (non-swappable) location for a long time will burn into the memory. (I know that I am reacting beside the point of your story, to which I agree.) Pimpin' Peters Papers: http://www.cypherpunks.to/~peter/usenix01.pdf -- A: No. Q: Should I include quotations after my reply? URL:http://www.subspacefield.org/~travis/ -- pgp8gThz9AZST.pgp Description: PGP signature
Skype reverse-engineering details]
Some very juicy details here: http://www.blackhat.com/presentations/bh-europe-06/bh-eu-06-biondi/bh-eu-06-biondi-up.pd -- Cryptography is nothing more than a mathematical framework for discussing various paranoid delusions. -- Don Alvarez URL:http://www.subspacefield.org/~travis/ -- ---BeginMessage--- Trying this again... hopefully the envelope sender gets set right. Some very juicy details here: http://www.blackhat.com/presentations/bh-europe-06/bh-eu-06-biondi/bh-eu-06-biondi-up.pd -- Cryptography is nothing more than a mathematical framework for discussing various paranoid delusions. -- Don Alvarez URL:http://www.subspacefield.org/~travis/ -- pgpDsDeOH8h78.pgp Description: PGP signature ---End Message--- pgpSmV0dqE60W.pgp Description: PGP signature
Re: Traffic Analysis References
On 10/19/06, Leandro Meiners [EMAIL PROTECTED] wrote: Can anybody point me to any good references regarding traffic analysis? This is the only interesting page I found on it: http://guh.nu/projects/ta/safeweb/safeweb.html There are some historical incidents that are sufficiently old to be unclassified: For example, the Japanese left their normal morse operators behind when setting sail for Pearl Harbor. They continued to send transmissions as though they were still in Japan's waters. Morse operators are fairly identifiable by their rhythm and idiosyncrasies, known collectively as their fist. It's just like any other behavior performed subconsciously, like typing or signing your name; at first there's a lot of variation, and later it becomes fairly fixed and potentially identifying. Also during WWII, a year before D-Day, the Allies in Scotland created a radio net that purported to be a [nonexistent] 4th Army, ostensibly to feint towards southern Norway. The purpose behind this was to further dilute Axis forces, to keep them far enough away to be unable to participate around Normandy (there were, obviously, numerous deception operations around D-Day). This last bit is well documented in The Codebreakers, which also has numerous entries in its appendix for Traffic Analysis. I suspect that in many instances where traffic analysis was useful, it was necessary to make (or learn) certain assumptions about typical traffic patterns; that is, orders come from the top and are disseminated down the military hierarchy, etc.; that requests for supplies, battle damage assessments, and other feedback flows up from the front-line troops to the logistic units or field commanders; that traffic increases as one approaches a major military operation, etc. In other words, it's context-specific, and may resist generalization into easily-remembered axioms. Also, the mixmaster and cypherpunk remailers, ATT's crowds, and the onion-routing groups, probably have some papers considering various traffic analysis and correlation attacks against those systems since they are encrypted inside the mixers. One thing I have been interested in is the security of typical plaintext Internet protocols when secured with SSL/TLS/IPSec. If they don't do any padding, then the length of each step of the protocol is effectively given away; just count how much data passes to the recipient before data starts flowing in the opposite direction. Also, there is timing information, and it is fairly well preserved even across the Internet (see the timing side channel attacks against SSL). Even if there is padding, which is basically wasted bandwidth, it may still be possible to discern information. I've been thinking about this, and I am not sure how to entirely avoid it without running into other problems. For example, Unix's configuration files and application-level TCP/IP protocols are very easy to interpret and troubleshoot thanks to their human-readable strings. The typical encrypted protocol uses non-textual, constant-length messages, which can make it difficult to extend without introducing incompatibilities (or even making different responses different lengths again, the worst of both worlds). One doesn't typically need very extensive decoding algorithms in order to make the plaintext data human-readable, which is good because those decoding libraries are also processing data from remote (untrusted) entities and form part of the attackable surface, and have proven to be security holes on more than one occasion. One alternative I came up with is to send the entire catalog of possible responses at the beginning of the transmission, then refer to them by a fixed-length index. This would be a lot of overhead in many cases. Another alternative is to have a standard catalog, something like an MIB, that may be cached between invocations. Nevertheless, there are many times during a protocol that you wish to dynamically construct a response without knowing it a priori; it would seem difficult to deal with those cases in any other way. These approaches could be implemented simultaneously, and perhaps one only needs to pad when sending variable-length messages, so that normal common messages don't incur any overhead (at the cost of fixed-length and variable-length messages being distinguishable sets, but not distinguishable individually). In this way it is similar to what cryptologists were doing with telegraph codebooks, which encoded standard phrases in relatively similarly sized units, but had to spell out anything not in the codebook using many codes (each signifying one letter or part of a word). If you come across any other links, please let me know as I'd like to add them to my page on side-channel attacks: http://www.subspacefield.org/~travis/side_channel_attacks.html -- It's not like I'm encrypting... it's just that my communications developed a massive entropy deficiency. -- URL:http://www.subspacefield.org/~travis/ GPG
hashes on restricted domains: random functions or permutations?
So I was reading about the OTP system (based on S/Key) described in RFC 2289. It basically hashes a secret several times (with salt to individualize it) and stores the value that the correct password will hash to. Now my question is, if we restrict ourselves to, say, 160-bit inputs, is SHA-1 a permutation, or do collisions exist? If there are collisions, then iterating the hash could lead to fewer possible values each time, potentially converging on a set of inputs that form a permutation and are closed under composition. Is that correct? What are the expected sizes of such sets? Is it worth worrying about? -- The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.'' [sic] -- Bill Gates -- URL:http://www.subspacefield.org/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: handling weak keys using random selection and CSPRNGs
On 10/12/06, Leichter, Jerry [EMAIL PROTECTED] wrote: Beyond that: Are weak keys even detectable using a ciphertext-only attack (beyond simply trying them - but that can be done with *any* small set of keys)? Yes, generally, that's the definition of a weak key. But that's an odd attack to defend against - why not just try all the weak keys (or, again, any small subset of keys) and see if they work? Because that's the definition of brute forcing, and generally the key distribution is close to uniform in any [symmetric] system that is worth a second glance? do continuous online testing: Compute the entropy of the generated ciphertext, and its correlation with the plaintext, and sound an alarm if what you're getting looks wrong. This is a decent idea. Of course, there are scads of problems that are not detectable by a simple memoryless markov model, but this would be a decent sanity check on all but the smallest of plaintexts. I would also want continuous monitoring of my HWRNG outputs; maybe I wouldn't want a simple entropy check, which a properly-functioning HWRNG will fail with a probability predicted by chance, but perhaps a graphical display of the previous values. I'm not a visual thinker, but I don't think any amount of statistics are going to be as useful in detecting deviations from uniformity as a plot and a human brain. -- The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.'' [sic] -- Bill Gates -- URL:http://www.subspacefield.org/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: TPM disk crypto
On 10/9/06, Adam Back [EMAIL PROTECTED] wrote: The bad part is that the user is not given control to modify the hash and attest as if it were the original so that he can insert his own code, debug, modify etc. (All that is needed is a debug option in the BIOS to do this that only the user can change, via BIOS setup.) Actually, it's the BIOS I don't trust. I can validate everything else, but as long as the BIOS is motherboard-specific and closed source, I don't see why I should trust it. We need to get rid of this legacy crud. LinuxBIOS is a good step but unfortunately it is only supported on a few motherboards. No BIOS I know of has a semblance of security, given temporary physical access to the machine. BTW, the x86 microcode updates are performed by the BIOS IIRC and require no hardware settings. Is there any reason you can't update the processor microcode later on in the boot process? -- The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.'' [sic] -- Bill Gates -- URL:http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
deriving multiple keys from one passphrase
What is the accepted way to derive several keys from a user-supplied input? Or, can you see anything wrong by prepending a counter to the passphrase and hashing it to create derived keys? k_n = hash(n || passphrase) I suppose a faster system would involve using hash(passphrase) as the key and encrypting a counter (assuming that hashes are slower than block ciphers). k_n = E(hash(passphrase), n) Both seem vulnerable to dictionary attacks, and it's not immediately clear to me how I could prevent them, or if that's even possible. Terry Ritter suggested using CRCs over the passphrase, but I haven't really analyzed that method at all. Any opinions? -- Enhance your calm, fellow citizen; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Discussion of SIGABA, FPGA query, automated cipher construction, c.
First, I found this interesting site by John Savard which discusses the various crypto designs since... well, since pencil and paper systems. Notable is the detailed discussion of the declassified SIGABA machine: http://www.quadibloc.com/crypto/jscrypt.htm Next, can anyone point me in the direction of any web references on using FPGAs to implement cryptographic (or other) algorithms? I would like the speed of hardware, but feel that it is necessary to amend the algorithms as the state of the art advances. I've also wanted to do some low-level hardware interfacing. Have there been any attempts to construct ciphers based on a key or random number? It would be interesting to see a family of ciphers from which one is chosen periodically, in addition to re-keying. I suppose that one could permute S-tables in Feistel-type ciphers fairly easily (a la traditional Unix crypt() salt), but have there been any more general efforts, perhaps using virtual machines or lisp? I do realize that an algorithm is already parameterized by the key, but the general structure remains the same. I found this amazing paper on sandboxing x86 code (software-based fault isolation), and due to some engineering the overhead is pretty minimal (20% on SPECint2000): http://www.usenix.org/events/sec06/tech/mccamant.html Using a method like this between two systems with the same instruction set, the crypto protocol initiator could even send the algorithm they want to use to encrypt, compress, or otherwise transform the rest of the session, and the recipient could ostensibly execute it safely, and vice-versa. If any of you are die-hard assembly or algorithm mavens, this book might interest you: http://www.amazon.com/Hackers-Delight-Henry-Warren-Jr/dp/0201914654 -- Enhance your calm, fellow citizen; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
handling weak keys using random selection and CSPRNGs
Hi all, It occured to me that there is a half-decent way to avoid weak keys in algorithms when it is undesirable or impossible to prompt the user for a different passphrase. It is even field-upgradable if new weak keys are found. Basically, instead of using the hash of the passphrase up front, you do a PRNG expansion of the passphrase. For example, k_1 = hash(1||passphrase) k_2 = hash(2||passphrase) and so on. The important thing here is that it is not something like the following: k_1 = hash(passphrase) k_2 = hash(k_1) ... k_n = hash(k_(n-1) In that method, the number of input states is limited by the hash size, whereas the former algorithm has a number of states that the k sequence can be in is limited by the size of the passphrase. I suppose that a running hash would be limited by the size of the hash state (chaining variables). Next you construct k = k_1 || k_2 || ... k_n The computation can be done incrementally on an as-needed basis. Then, you read in the number of weak keys, and perform a random selection on the number of valid keys using the algorithm I posted earlier, with k as the source of unpredictability. This leaves you with a random number between 0 and the number of non-weak keys minus one. Then you iterate over the weak keys in numerical order, incrementing the value from the previous step by one if it exceeds the weak key's numerical value. This part runs in time linear with the number of weak keys, not the size of the non-weak keyspace. You are left with a value that has a uniform distribution over the non-weak keys. The random selection algorithm may run indefinitely, but the chances of that are infinitesimal. If there are a huge number of weak keys, then it may take longer, but I'd be willing to bet that CPU speed increases faster than discovery of weak keys, and if it doesn't the user might be inconvenienced enough to upgrade to a less broken cipher algorithm. -- The obvious mathematical breakthrough would be the development of an easy way to factor large prime numbers.'' [sic] -- Bill Gates -- URL:http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: TPM disk crypto
On 10/2/06, Erik Tews [EMAIL PROTECTED] wrote: Am Sonntag, den 01.10.2006, 23:42 -0500 schrieb Travis H.: Anyone have any information on how to develop TPM software? http://tpm4java.datenzone.de/ Using this lib, you need less than 10 lines of java-code for doing some simple tpm operations. Interesting, but not what I meant. I want to program the chip to verify that the BIOS, boot sector, root partition conform to *my* specification. I don't want binary-only hardware-enforced vendor lock-in, that went out of fashion with the mainframe and proprietary data[base] formats. -- TH - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: TPM disk crypto
On 10/5/06, Erik Tews [EMAIL PROTECTED] wrote: First, you need a system with tpm. I assume you are running linux. Then you boot your linux-kernel and an initrd using the trusted grub bootloader. Your bios will report the checksum of trusted grub to the tpm before giving control to your grub bootloader. Your grub bootloader will then report the checksum of your kernel and your initrd to the tpm before giving control to them. Awesome, that's incredibly useful information. I had not heard of trusted grub. Thanks! One thing you should know is, that a tpm can never find out, if a software meets some specifications, like does not have an buffer overflow or does not execute code from the network or so. You just can check is has not been altered. Of course. However, you can sandbox x86 code efficiently: http://www.usenix.org/events/sec06/tech/mccamant/mccamant_html/index.html -- Enhance your calm, fellow citizen; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
wanted: mod arith equivalences/tautologies
Hey does anyone have a good link for the various equivalencies (or inequivalencies) for modular arithmetic? I realize some will only apply to certain moduli, especially primes. I'm basically wanting to find some good algorithms for certain simple computations, like f(x) = ax + b (mod n), or the BPP digit extractor for Pi, but for very large values. I'm hoping to do them in ocaml or python. -- Enhance your calm, fellow citizen; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
TPM disk crypto
Quoting: Disk drives gear up for a lockdown Rick Merritt, EE Times (09/25/2006 9:00 AM EDT) Built-in security is the next big thing for hard-disk drives. By 2008, drive makers should be shipping in volume a broad array of drives based on a maturing standard. ... The first version of the Trusted Computing Group's standard for disk drive security could be completed by year's end. Seagate Technology Inc. already ships one drive with an integrated security chip, although some see that approach as an interim step. For mass production, security has to be integrated into the controller. It's not that many gates, even if the function is not used, said A. Currie Munce, vice president of research for Hitachi Global Storage Technologies. Seagate CTO Mark Kryder agreed, saying his company will integrate security functions in the drive controller very soon. A security standard will open the door to selling drives preloaded with content that users can unlock after paying online for a digital key...' === Anyone know if this is going to be compatible with the IEEE SISWG standard? Anyone have any information on how to develop TPM software? Anyone else recognize how features migrate from the CPU to an add-on card and back to the CPU? Same thing happened with RAID and on-board video and so on... it seems to me that people need an open-source add-in card for crypto, perhaps based around an FPGA, that is updatable if the algorithms need strengthening. It seems that Peter Gutmann has already done something similar: http://www.cypherpunks.to/~peter/usenix00.pdf -- Enhance your calm, fellow citizen; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
The Geheimschreiber Secret - Swedish WWII SIGINT
http://frode.home.cern.ch/frode/ulfving/ulfving.html This discusses Swedish decryption of a German crypto machine. Although the break was done without any hints, it was a fairly straightforward system of long-period XOR and fixed transposition, and eventual success was predicated on the laziness of the operators (what else is new?). Perhaps someone can make this into some form of game-theoretic research paper. An interesting economic commentary, if somewhat off-topic, is: ``Many analysts consider that war preparations serve only as instruments of pressure during negotiations. However, that ignore the dynamics of future military developments which are created by a deployment as large as that which occurred here. Economic factors and military logistics make it almost impossible to keep large, inactive troop concentrations in place as a trump card during long negotiations, just as it is damaging for the units' fighting spirit. It is too expensive not to use the troops, therefore they must either be used in combat or be demobilized and returned to civilian life. Only victory justifies the price -- even if it is high. For example, consider the collapse of the economic, political and ecological systems now affecting the states of the former Soviet Union as a consequence, during a long period, of a highly forced ``war economy'' that did not result in any gains.'' Perhaps the mission creep seen in most large bureaucracies need not always be attributed to power-grabs and personal aspirations of department leaders, but to relatively benign economic arguments that we already pay for it, we might as well use it. Along with the idea that capabilities must periodically be exercised in order to prevent atrophy, that probably explains a lot of otherwise puzzling decisions and apparent over-reactions on the part of decision-makers. -- Enhance your calm, fellow citizen; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A note on vendor reaction speed to the e=3 problem
On 9/26/06, Richard Salz [EMAIL PROTECTED] wrote: Really, what? There are things it doesn't do, but since it's only a packaging format that's a good thing. Though there are unshar tools, typically people run it as input to /bin/sh, usually without reading through it (and given the level of obfuscation sh offers, it's not clear that you couldn't sneak something through even if the person skims it). -- Enhance your calm, brother; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A note on vendor reaction speed to the e=3 problem
On 9/15/06, Taral [EMAIL PROTECTED] wrote: *That* is the Right Way To Do It. If there are variable parts (like hash OID, perhaps), parse them out, then regenerate the signature data and compare it byte-for-byte with the decrypted signature. You know, this sort of reminds me of a problem with signatures on tar.gz files. Basically, you have to keep them around so you can check the signature, but you can't delete them because you can't reconstruct the original tar file from an untarred copy because it's full of metadata that won't necessarily be replicated on your system. For example, uids and gids. Unfortunately, cpio appears to be worse. From a tape backup standpoint, tar doesn't store enough (extended attributes, hard links, etc.) and so it appears to store both too much and too little at once. It would be nice if there was a format other than shar which was deterministic and only contained the contents of the files; no metadata. Then we could sign the code and nothing else. From a security point of view, shar has obvious problems :-) Anyone know of a relevant tool? -- Enhance your calm, brother; it's just ones and zeroes. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
On 9/9/06, Adam Back [EMAIL PROTECTED] wrote: IGE if this description summarized by Travis is correct, appears to be a re-invention of Anton Stiglic and my proposed FREE-MAC mode. However the FREE-MAC mode (below described as IGE) was broken back in Mar 2000 or maybe earlier by Gligor, Donescu and Iorga. I recommend you do not use it. There are simple attacks which allow you to manipulate ciphertext blocks with XOR of a few blocks and get error recovery a few blocks later; and of course with free-mac error recovery means the MAC is broken, because the last block is undisturbed. http://groups.google.ca/group/sci.crypt/browse_thread/thread/e1b9339bf9fb5060/62ced37bb9713a39?lnk=st I don't see why integrity+confidentiality has to cost n log n operations. I haven't read the whole paper yet (and the proof is at the end), but I don't see why you can't append a universal hash (chosen by a second key, or at random and identified in the plaintext in some suitable way) of the input to the plaintext prior to encryption, and get integrity for cheap. Or are universal hashes considered cryptographic-weight primitives, and thus this constitutes a second pass over the plaintext? I must admit I don't know of any lower bound on universal hash complexity... wikipedia only mentions f(x) = ax + b mod p, (p prime) which is clearly less heavy than modexp and other PK algos, and it looks like you could do it incrementally over the plaintext x, I think... my intuition tells me this is way faster than a block cipher. -- On the Internet noone knows you're a dog - except Bruce Schneier. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Did Hezbollah use SIGINT against Israel?
On 9/20/06, Leichter, Jerry [EMAIL PROTECTED] wrote: Newspaper reports have claimed that many troops were sent into the field with old equipment - including in particular 10+-year-old communications equipment. The Single Channel Ground and Airborne Radio System was designed in the 80's: http://www.fas.org/man/dod-101/sys/land/sincgars.htm I don't know the hop frequency, but it's probably smaller than modern standards (could possibly be followed with real-time tracking), it probably uses a manually-entered seed to generate a hop sequence, the PRNG that stretches the seed is probably not secure any more, and the input space is probably searchable by now in a reasonable amount of time. Further, once broken with some expensive hardware (maybe a custom-designed SIGINT SDR), they could program much cheaper units to follow the sequence until the Israelis re-keyed. Just my total guess. -- On the Internet noone knows you're a dog - except Bruce Schneier. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: RSA SecurID SID800 Token vulnerable by design
On 9/15/06, Daniel Carosone [EMAIL PROTECTED] wrote: But let's not also forget that these criticisms apply approximately equally to smart card deployments with readers that lack a dedicated pinpad and signing display. This looks mildly interesting: http://www.projectblackdog.com/product.html I guess it uses an autorun file on Windows; I wonder whether most systems allow you to effectively launch X. The docs say it connects via ethernet over USB, so you're effectively a thin X client. Nice that it's open-source. Good idea, still vulnerable to software surveillance and host OS. No display. This looks more interesting: http://fingergear.com/bio_computer_on_a_stick.php This has a display, a fingerprint reader, runs Linux, has many common apps (office-compatible suite), IM, etc. More relevant to the list, it has a OTP generator, so this is effectively a security token. See: http://fingergear.com/faq1.php#4 Unfortunately, it looks like you can't reimage it without wiping everything, and then you lose the OS. I hope you can get a modifiable OS image and install it just as one would save data to the USB drive, but it could be impossible. The worst cost for these more advanced methods may be in user acceptance: having to type one or more things into the token, and then the response into the computer. A USB connected token could improve on this by transporting the challenge and response, displaying the challenge while leaving the pinpad for authentication and approval. I wonder if the ubiquitous fingerprint reader could replace the need for lots of buttons; controls tend to be the most expensive and fragile part of electronic devices. I wonder why nobody has an open-source cell phone that does voice recognition yet. That would seem to be the ideal solution, wouldn't it? You're already carrying one around, and you have a keypad for dialing (can be used for PIN), LCD panel for output, and if you have a fingerprint reader, enough juice to perform some crypto, and a USB or bluetooth connector (for storage and communication) it'd be perfect. -- On the Internet noone knows you're a dog - except Bruce Schneier. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: IGE mode is broken (Re: IGE mode in OpenSSL)
On 9/10/06, James A. Donald [EMAIL PROTECTED] wrote: Typo: We transmit T(k)= {W(k)} + W(k-1)|{W(k-1)} where | means bitwise or, curly brace means encryption. Should read: We transmit T(k) = {W(k)} + ((~W(k-11){W(k-1)}) where ~ means bitwise negation, | means bitwise or, curly brace means encryption. Today wasn't a good day for typing? ;-) T(k) = {W(k)} + (~W(k-1)|{W(k-1)}) Right? I'm in agreement with the don't use a screwdriver as a crowbar crowd; unless the combined modes came with clear proofs and very weak assumptions computers are fast and getting faster, and my performance needs remain relatively constant. -- On the Internet noone knows you're a dog - except Bruce Schneier. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
secure key storage APIs
Hey, Does anyone know of any OSS OS facilities for managing keys? With ssh-agent and gpg-agent providing access to key storage by inherited processes, and the keys themselves being vulnerable as stored on-disk, I wonder if there isn't any more general facility for doing key management and access control, and I was wondering if there were any useful papers on this kind of facility. As I see it, there are a couple of seperate issues: 1) Persistent key storage; how does it look on-disk? Obviously we will want confidentiality, and probably have integrity. But what kind of algorithm do we use? When designing key storage for a given system, one can usually use that system to access the persistent form. This has the neat property that a break in the storage security would imply that the given system itself could have been broken, so no harm done; the attack surface is not increased by the key store subsystem. 2) Non-persistent key store; there are data remanence issues with DRAM and other supposedly non-persistent storage. I have heard a story about a homebrew computer that stored the clean shutdown or dirty bit in the same memory location, and after a reboot it would read this location to decide if it needed to check the disks. Apparently it stayed dirty so long the value was burned-in. Maybe not a big deal for key store in a complex environment, but would be really important in embedded devices with fairly static memory layouts, e.g. VPN concentrators. Solve by secret-sharing between two locations, or by inverting every bit periodically. 3) Access control policy; who should get access to the keys? 4) OS support; should keys be stored as immutable quantities, like a process's real UID value? If so, can they be transferred, and under what conditions? Can they be inherited? Any considerations that I'm missing? -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
link fest on fingerprint biometrics
Found at doxpara.com: fingerprints: http://chris.fornax.net/biometrics.html faceprints: http://www.site.uottawa.ca/~adler/publications/2003/adler-2003-fr-templates.pdf More on fingerprints: http://onin.com/fp/cyanoho.html At home I have an excellent page on making fake fingerprints, but I cannot find it right now. It used gelatin (like jello) and was successful at fooling a sensor. I did find this, which reports success with gummi bears: http://msn.pcworld.com/article/id,116573-page,5/article.html This says play-doh works on Walmart and Target sensors: http://digg.com/security/Play-Doh_Beats_Wal*Mart_s_and_Target_s_Fingerprint_Scanners?cshow=927041 Or more generally: http://www.linuxelectrons.com/article.php/20051209175034721 More about fingerprints: http://www.latent-prints.com/ If anyone can give me any fingerprint-related links, particularly about spoofing/breaking them, I would be grateful. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
signing all outbound email
Has anyone created hooks in MTAs so that they automagically sign outbound email, so that you can stop forgery spam via a SRV DNS record? -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: IGE mode in OpenSSL
Nevermind the algorithm, I saw the second PDF. For the other readers, the algorithm in more standard variable names is: c_i = f_K(p_i xor c_(i-1)) xor p_(i-1) IV = p_(-1), c_(-1) I suppose the dependency on c_(i-1) and p_(i-1) is the part that prevents the attacker from predicting and controlling the garble. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: IGE mode in OpenSSL
The NIST server is down. Care to post the algorithm? By the term crib do you mean a known-plaintext? I'd like to see a proof that it is not possible to alter the final block to make it decrypt to all zeroes; that seems worse than CRCs and putting a CRC at the end of the plaintext is a common, and often broken, way to do integrity checking, because it's linear and allows the opponent to toggle bits in the plaintext and fix the CRC without breaking the encryption. I don't see how appending a hash of the plaintext could be a crib. The encryption prevents the opponent from knowing the plaintext, so he wouldn't know what the hash preimage is. If you encrypt the hash, you basically have HMAC without using a keyed hash. There are block modes that do integrity and encryption at the same time; does this offer and advantage over them, and if so how? -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Debunking the PGP backdoor myth for good. [was RE: Hypothesis: PGP backdoor (was: A security bug in PGP products?)]
On 8/28/06, Ondrej Mikle [EMAIL PROTECTED] wrote: Take as an example group of Z_p* with p prime (in another words: DLP). The triplet (Z, p, generator g) is a compression of a string of p-1 numbers, each number about log2(p) bits. Pardon my mathematical ignorance, but isn't Z just a notation to indicate a ring, as opposed to a parameter that you'd have to store? -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
uniformly random selection algorithms
I didn't know about this RFC, but apparently the IETF has a standard for selecting people randomly for sortition in a publicly-verifiable way. References: http://rfc.sunsite.dk/rfc/rfc3797.html http://www.isi.edu/in-notes/rfc3797.txt This got me to thinking about random selection. They take several publicly-verifiable randomly generated numbers (such as government-run lotteries), concatenate them in an unambiguous way, and then hash each one (with a sequence number prefixed and suffixed), treat the results as a 128-bit big-endian integer, and take the remainder after division by the remaining pool size (i.e. without replacement). However, there's a slight bias for people towards the front of the pool; for demonstration, assume we start with a uniformly random 8-bit number instead of 128-bit, on a pool size of 100. These numbers are selected to exaggerate the bias. The first 55 people have 3 opportunities to win; person 0 has 0, 100, and 200. However, person 56 has only two; 56 and 156. It's a minor point for small pools and 128-bit integers, but wouldn't it be mathematically more uniform to create a pseudorandom stream from the hashed outputs and then apply one of the following algorithms? Assume a pool size p, lg means binary logarithm, n=ceil(lg(p)) and x is an unsigned big-endian integer: 1. Trial-and-error: x = extraction of n bits If x p, then return x. Otherwise, discard and repeat. 2. This algorithm seems to waste fewer bits: Initialize with c = 0. x = extraction of n bits. Let y = x+c If y p, then return y Otherwise, let c = y - p Go back to the extraction step. 3. This may be more efficient still; Pick b such that 2^b p (e.g. p=100, b=128) Let q = floor(2^b/p) y = one of the earlier algorithms with p=pq Return y mod n In this last algorithm, b is chosen to be a computationally-convenient size (e.g. size of the hash output). PS: In case anyone doesn't know, Lynn Wheeler's RFC index is amazing. Best RFC interface ever: http://www.garlic.com/~lynn/rfcietff.htm -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
correction to uniformly random selection algorithms
I just realized I made a small error in algorithm 2. On 9/2/06, Travis H. [EMAIL PROTECTED] wrote: 2. This algorithm seems to waste fewer bits: Initialize with c = 0. x = extraction of n bits That should read: x = extraction of ceil(lg(p-c)) bits Otherwise there's nothing gained by carrying the remainder c. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: A security bug in PGP products?
On 8/23/06, Dave Korn [EMAIL PROTECTED] wrote: Given that, whatever passphrase you use, you will decrypt the EDK block and get /something/ that looks like a key, this comparison of hashes is a sanity test. If you bypass it but enter the wrong passphrase, you'll get an incorrectly-decrypted EDK, which will lead your disk to look like every sector is full of random garbage. Rather than decrypt the entire disk and run chkdsk to see if it looks sane, comparing the hashes of the passphrase is a quick and dirty way of testing if the resulting EDK is going to be the correct one. The PGP email encryption has two known-plaintext bytes for that purpose. This only honors a bad key 2^16 of the time, but ensures that brute-forcing must do a more extensive unknown-plaintext attack at that rate for any potentially-correct key. This reminds me a little of the suggestions that MACs should be truncated, although it seems to me that it's better to encrypt a hash of the plaintext. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Hypothesis: PGP backdoor (was: A security bug in PGP products?)
On 8/23/06, Ondrej Mikle [EMAIL PROTECTED] wrote: We discussed with V. Klima about the recent bug in PGPdisk that allowed extraction of key and data without the knowledge of passphrase. I skimmed the URL and it appears this claim was answered several times in the original thread. Did you not read it, or not understand it? You have to have a valid passphrase from before the change, because the passphrase unlocks the disk key which doesn't change, unless you explicitly tell it to. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: compressing randomly-generated numbers
On 8/29/06, Alexander Klimov [EMAIL PROTECTED] wrote: Well, it not really a claim since there was no definition, here it is: A ``dependency stripping'' algorithm is a deterministic algorithm that gets a stream of unbiased (but not necessary independent bits) and produces a stream of several independent bits. Well, this is a fairly strict definition, I think uniform and e-close to independent is still potentially suitable for use in cryptography. or a computationally-pseudorandom stream, This requires a random key. I can't use e-close to (uniform and independent)? Recall that the whole point was to extract random bits -- if we already have useful random bits we can simply output them and discard the input stream. I hear this argument often, and it appears that the people who say it don't care about the rate of random bits, nor the desirability of not having to trust any one source to be truly unpredictable, nor have they understood the point of an extractor or hashing the output of multiple sources. For example, I'd like to use the Quantis HWRNG, but since it is an opaque container, then I cannot trust it fully. If I had another source that I could combine with it, then I do not have to trust it blindly; the opponent would have to compromise both in order to be able to predict the combined output. Consider ``x a x b x c x ...'', sampling every other bit throws away most of entropy. In general, there is no ``dependency stripping'' algorithm because an input x,x,x,..., where all x are the same (either all 0 or all 1), is possible. There is simply no enough entropy in the input to extract at least two bits. No, you have no idea of the unpredictability of that source, because it is unspecified and unpredictability is untestable. That could very well be the output of a perfect HWRNG. So could 01010101, or 000, or 111. Each output is equally likely, and no amount of testing the output can say whether the source is imperfectly random or truly random. This was stated several times on this list; entropy depends on the model of the source, not on the output. The sequence: 0, 1, 2, 3, 4... 255, 0, 1, 2, 3, 4... 255 ... has a zero entropy if the source is defined as an 8-bit counter starting at zero, and it has an entropy of 1 if the source is defined as a HWRNG that generates 8-bit outputs in a uniform and independent manner. Re-read the definition of entropy, and pay particular attention to the calculation of probability for a given event. Interestingly, an additional requirement that the input stream has at least two bits of entropy does not change the situation I didn't understand this example. See above about ``sampling at a slower rate.'' I can take an analog random source, and sample it at one rate, and have a nearly independent stream. If I increase the sample rate, the bits will start to become more and more dependent upon the prior bit. So, if that is true, then logically a serially-correlated stream will become less and less correlated as I decrease the sample rate. Taking every other bit corresponds to sampling at half the speed, but doesn't require modifying the hardware. It seems that you are saying there is no general solution, given a total lack of knowledge about the source other than the fact that there is some dependency between the bits. I can agree with that. However, if you understand the physics of the source, then you do know something about the random phenomenon used as a source, and in that case you can eliminate specific kinds of dependencies that it may exhibit. The easiest way to eliminate (computationally) bias and dependency in one step is to combine with a CSPRNG. You can reseed it periodically with the combined output. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Hamiltonian path as protection against DOS.
What is the complexity class for Eulerian paths/trails? Wikipedia doesn't say. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
collisions in 64 round variant of SHA-1 with 25% chosen plaintext
http://www.heise-security.co.uk/news/77244 ``Although the demonstration was restricted to the reduced SHA-1 variant in 64 steps, it can, according to the experts, also be generalised to the standard 80 step variant. This means that SHA-1 must also be considered as cracked in principle. Christian Rechberger, who developed the new attack together with his colleague Christophe De Cannière, explained to heise Security that, in their experiments, up to one quarter of the message could be freely selected. The remaining 75 percent is, as before, determined by the attack. Rechberger suspects, however, that the amount that can be freely selected can be further increased by optimising the attack.'' -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
CRCs and passphrase hashing
Howdy! I was talking to Terry Ritter, and he was explaining to me that when he needed to make some keys from a user-supplied passphrase, he computed various CRCs over the passphrase, and used those as derived keys. I'd like to know more about it, and I was wondering if anyone knew of any work that addressed the strength of this kind of passphrase preprocessing. Forgive me for not being able to hit the ground running after reading the explanation from mathworld, as I don't have a degree in discrete math. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [IP] more on Can you be compelled to give a password?
On 8/8/06, Ed Gerck [EMAIL PROTECTED] wrote: The worst-case setting for the user is likely to be when the coercer can do all that you said and has the time/resources to do them. However, if the distress password is strong (ie, not breakable within the time/resources available to the coercer), the distress password can be used (for example) to create a key that decrypts a part of the code in the binary data that says the distress password expired at an earlier date -- whereas the access password would create a key that decrypts another part of the code. So the opponent then knows the password given to him is not valid, and might continue to search for a current one. And/or step through the program with a debugger, like a software cracker removes copyright protection. There are other possibilities as well. For example, if the binary data contains code that requires connection to a server (for example, to supply the calculation of some function), that server can prevent any further access, even if the access password is entered, after the distress password is given. The data becomes inaccessible even if the coercer has the binary data. Or, nobody has the data: http://monolith.sourceforge.net/ http://www.schneier.com/blog/archives/2006/03/monolith.html It seems clear that the data used to create the protected plaintext has to be only completely in the hands of the opponent, to prevent its use, or to mediate the exchange in some active sort of way. Perhaps tamper-resistant hardware like the crypto iButton could play a part here (it's FIPS-140 rated, under $75 for a single unit, and can be programmed in java). Sometimes it's better that you aren't able to do something... so that you can't be compelled to do it, like having a time-lock on a bank vault. The way to do that is tamper-resistant hardware and/or trusted computing, so that you don't care (much) if the opponent acquires it, too. Elaborating on your idea of the two keys decrypt different parts of the ciphertext, the iButton spits out keys that are used in a steganographic file system, so that the duress password gives one set of innocuous data and silently zeroizes the real stego key, while the real password yields the real key to the stegfs, and nobody can prove anything about the protected plaintext without that key -- that's crucial to deceiving the opponent that the duress password was indeed genuine, which prevents you from being punished for giving a duress password post-facto. Wiping the ciphertext gives away the gambit, but in cases where one doesn't care about that then it wouldn't be a bad idea. Couple this with a dead-man's switch; you have to use the ibutton every two weeks or else it deletes the real key upon next power-up. Now you need merely do nothing for two weeks to defeat the opponent. If forced to use it, one uses the duress password, and opponent is defeated without him knowing. If the tamper-resistant hardware has a power supply and clock, it can zeroize itself after two weeks, instead of waiting for the next power-up, which is important if one wants to have a short window for attacking the hardware. Alternately, the system containing the ciphertext needs to be powered on and running an internal clock. Another method involves a tamper-resistant token a la SecureID, in which case keys generated in odd minutes are duress keys, and keys generated on even minutes are real keys. Or vice-versa of course. Those lacking tamper-resistant hardware could substitute a system running at a remote location for said hardware. A related link is the cryptography using simulated satellites, or something like that... Fast data-deletion is a good case where information-theoretic security is undesirable; one wants a small key (relative to the plaintext), so that zeroization is fast and requires little power by the embedded hardware under attack. This suggests ECC at the present -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [IP] more on Can you be compelled to give a password?
On 8/9/06, Ed Gerck [EMAIL PROTECTED] wrote: A debugger cannot decrypt without the key, which is produced only with the access password. Ah okay. By the way, an interesting link from Schneier's blog, mentions copyright and randomly-generated numbers: http://ansuz.sooke.bc.ca/lawpoli/colour/2004061001.php -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: [IP] more on Can you be compelled to give a password?
On 8/8/06, Travis H. [EMAIL PROTECTED] wrote: Or, nobody has the data: http://monolith.sourceforge.net/ http://www.schneier.com/blog/archives/2006/03/monolith.html Grr... remind me not to read the comments on old blogs, it's irritating to see so much misrepresentation... The monolith model is being misrepresented. The problem is this: User A publishes fileA.mono, a file of apparently randomly-generated bytes. That's all the information you have. Has he, or has he not, infringed copyright? You must be answer this question before going after him. So you do some research, and find (among other things), user B's fileB.mono and user C's fileC.mono, both apparently randomly-generated. fileB.mono XOR fileA.mono yields a copyrighted work. fileC.mono XOR fileA.mono to produce something in the public domain. Now, who has committed what crime? Things get even more complicated with more files, and they need not bear .mono extensions. What is fileA.mono XOR fileB.mono XOR fileC.mono? Now add in ten thousand more files... I bet with the proper combinations you can create just about anything, and anyone at any time may create a file that when combined with another, is infringing. That is, Mallory may have published fileM.mono, and fileM.mono XOR fileC.mono is infringing; who is guilty of infringement, or framing the other user? Remember timestamps are trivially forged and lost during some copy operations, so you don't know who published first. You also don't know how they came up with their files, as bits don't have color. -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
compressing randomly-generated numbers
Hey, I was mulling over some old emails about randomly-generated numbers and realized that if I had an imperfectly random source (something less than 100% unpredictable), that compressing the output would compress it to the point where it was nearly so. Would there be any reason to choose one algorithm over another for this application? I recall talking to a CS prof once who said that LZW compression was optimal, which seemed and still seems really odd to me because optimal compression would generate a null output file. So surely he meant asymptotically optimal, or e-close to optimal, or something like that... anyone know? Obviously I will avoid any fixed-content headers and magic numbers by using a raw implementation of the algorithm, not reusing, say, gzip. Plus, I will be running as though the RNG was providing me with an infinitely long string, not reading everything into memory and trying to compress. It seems as though the Burroughs-Wheeler Transform (bzip2 et. al.) gets the best compression of the standard utilities... is it suitable for infinite length strings? Is there anything better? -- If you're not part of the solution, you're part of the precipitate. Unix guru for rent or hire -- http://www.lightconsulting.com/~travis/ GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: NIST hash function design competition
On 7/20/06, Florian Weimer [EMAIL PROTECTED] wrote: Is this about Colin Percival's work? The paper was by Dan Berstein; Percival's comments are specific to hyperthreading, but I think djb's research showed that it's applicable to non-HT architectures as well. -- Follow where reason leads -- Zeno || Unix guru for rent or hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Interesting bit of a quote
On 7/15/06, John Kelsey [EMAIL PROTECTED] wrote: Another solution is to use cryptographic audit logs. Bruce Schneier and I did some work on this several years ago, using a MAC to authenticate the current record as it's written, and a one-way function to derive the next key. (This idea was apparently developed by at least two other people independently.) Jason Holt has extended this idea to use digital signatures, which makes them far more practical. One caveat is that cryptographic audit logs only work if the logging machine is honest when the logs are written. Yeah, I love that idea, saw it at the 7th Usenix Security Symposium. For everyone else, there's an implementation here: http://isrl.cs.byu.edu/logcrypt/index.html I have been looking for something like this for a while. Note to Jason Holt: The subscribe links for the mailing lists are broken. I like the idea of encrypting the entries, but I thought that having to classify them into a finite number of classes, and restricting disclosure to be along class lines is restrictive, but I don't know offhand how to allow the logger to disclose arbitrary subsets efficiently. -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Interesting bit of a quote
On 7/14/06, David Mercer [EMAIL PROTECTED] wrote: WORM drives (and WORM tapes) are used by organizations that need to prove that things weren't altered (or to be able to audit when they are). The problem with this is determining if the media has been replaced. Absent other protections, one could simply write a new WORM media with falsified information. I can see two ways of dealing with this: 1) Some kind of physical authenticity, such as signing one's name on the media as they are produced (this assumes the signer is not corruptible), or applying a frangible difficult-to-duplicate seal of some kind (this assumes access controls on the seals). 2) Some kind of hash chain covering the contents, combined with publication of the hashes somewhere where they cannot be altered (e.g. publish hash periodically in a classified ad in a newspaper). -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: NIST hash function design competition
On 7/11/06, Hal Finney [EMAIL PROTECTED] wrote: : So what went wrong? Answer: NIST failed to recognize that table lookups : do not take constant time. âTable lookup: not vulnerable to timing : attacks, NIST stated in [19, Section 3.6.2]. NIST's statement was, : and is, incorrect. That's interesting, since it is in line with conventional reasoning about algorithms. I've skimmed his paper, and I've taken a class on computer architecture and I haven't the foggiest idea where the variable timing comes from. Does anyone know if any of the following account for the phenomenon? 1) cache fills as we ascend through memory 2) additions (base+index) taking non-constant time (could be fixed with pointers if we're going sequentially) 3) virtual memory considerations (e.g. fetching new a page for a higher address) 4) TLB misses Some more detailed discussion of CPU trends and how they affect hash performance is also welcome. How exactly does data pipelining affect hash run times more than a cipher? -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
timing attack biblio/link farm posted
I'm still fleshing it out, but I've gathered a bunch of links/papers on side-channel attacks: http://www.lightconsulting.com/~travis/side_channel_attacks.html Suggestions welcome. -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Correction: Side Channel Attack web page, was Re: timing attack biblio/link farm posted
Sorry, noticed the subject line was misleading. It contains every side channel attack I could find, including but not limited to timing. -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Interesting bit of a quote
On 7/11/06, Adam Fields [EMAIL PROTECTED] wrote: On Tue, Jul 11, 2006 at 01:02:27PM -0400, Leichter, Jerry wrote: Business ultimately depends on trust. There's some study out there - Trust is not quite the opposite of security (in the sense of an action, not as a state of being), but certainly they're mutually exclusive. If you have trust, you have no need for security. Quoting Ross Anderson's TCPA comments: A trusted [entity] is one that can break your security. Quoting John Carrol in Computer Security: Just because it is trusted, doesn't mean it's trustworthy. -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Quantum RNG (was: Use of TPM chip for RNG)
On 7/4/06, Taral [EMAIL PROTECTED] wrote: On 7/4/06, Andrea Pasquinucci [EMAIL PROTECTED] wrote: About RNG, does someone in the list have any comment, ideas on this http://www.idquantique.com/products/quantis.htm Why? Noise-based RNGs are just as random and just as quantum. :) Hella fast. Most of the RNGs based on electrical noise are not particularly pure -- some even use noisy diodes, which are decidedly predictable. Those that bother to isolate out one noise phenomenon or another sacrifice speed, and the average consumer won't have the technical background to judge them on anything else. Sampling faster gives more bits, but no more randomness. Overall, you're going to be limited by temperature with electrical noise phenomena. On the other hand, the quantis device appears to be simple, straightforward, and clean. But it's all sealed up in an opaque container. I asked them some questions about it and the person I was speaking with didn't seem to understand why anyone would care about what's in the module. Note that they sell QC endpoints as well. Very interesting company. -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Use of TPM chip for RNG?
On 7/3/06, Leichter, Jerry [EMAIL PROTECTED] wrote: You're damned if you do and damned if you don't. Would you want to use a hardware RNG that was *not* inside a tamper-proof package - i.e., inside of a package that allows someone to tamper with it? Yes. If someone has physical access to your equipment, they could compromise it. On the other hand, if you have access to it, you can establish a baseline and check it for changes. I recall the book titled Computer Security by Carroll suggested taking polaroids of all your equipment, and from each window, and other even more paranoid things. As a non-sequitur, in the first edition, he had the following wonderful quote on the dust jacket: ``Computer crime has become the glamor crime of the 1970s...'' Perhaps he was a bit ahead of his time. A spiked RNG of the kind you describe is at least somewhat fixable: Choose a fixed secret key and encrypt the output of the generator with the key before using it ... nor do you have to fix it for good.) Were you to periodically take the output of the generator and use it as a new key, you would have something remarkably similar to the fortuna and yarrow PRNGs. If you don't do something like that, you have cycle lengths equal to your input's cycle length, which for the designs we've been discussing, is fixed, so pretty easy to distinguish from random (assuming you have access to enough output). -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Use of TPM chip for RNG?
On 7/2/06, Peter Gutmann [EMAIL PROTECTED] wrote: You have to be pretty careful here. Most of the TPM chips are just rebadged smart cards, and the RNGs on those are often rather dubious. My last email of the day, I promise ;-) And if you're interested in some of the smart card developments, you might want to check out these proceedings: http://www.usenix.org/publications/library/proceedings/smartcard99/technical.html http://www.usenix.org/publications/library/proceedings/cardis02/tech.html -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: EDP (entropy distribution protocol), userland PRNG design
Going over old emails. On 10/12/05, Jack Lloyd [EMAIL PROTECTED] wrote: I prefer a multi-stage design, as described by various people smarter than I am: source(s) -- mixer -- pool -- extractor -- X9.31 Did you really mean X9.31 and not X9.17? -- Resolve is what distinguishes a person who has failed from a failure. Unix guru for sale or rent - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
classical crypto programmatic aids
Hi folks, Does anyone here know of any computer-based aids for breaking classical cryptosystems? I'm thinking in particular of the ones in Body of Secrets, which are so short that I really hope they're monoalphabetic substitutions. But I'm interested in these sorts of programs more generally. I could use paper, but it'd be nice if a computer could keep track of what I've tried and otherwise ruled out. I am aware of the crypt breaker's workbench, but that's specific to classic Unix crypt(3). What else is there? Incidentally, if anyone's interested, on my web page I have an article on how I used classical techniques to recover files encrypted with CFS and corrupted by disk failure or human error. It's sort of a rambling stream-of-consciousness that I wrote while learning CFS and breaking the encryption. It's not often that one gets to use classical methods against a modern cryptosystem, so I figure it may be refreshing. To summarize, CFS XORs each file against an eight-byte IV that is stored as a dangling symlink, and on my system the symlinks had become desynchronized from the files. PDF: http://www.usenix.org/publications/login/2004-08/pdfs/howard.pdf TXT: http://www.lightconsulting.com/~travis/cfs_travails.txt -- I sometimes have delusions of adequacy -- Woody Allen Security guru for rent or hire - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
complexity classes and crypto algorithms
What kind of problems do people run into when they try to make cryptographic algorithms that reduce to problems of known complexity? I'm expecting that the literature is full of such attempts, and one could probably spend a lifetime reading up on them, but I have other plans and would appreciate a summary. In particular, it seems like you should be able to make a respectable one-way function out of 3SAT. -- Whom computers would destroy, they must first drive mad. Security guru for rent or hire - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Status of attacks on AES?
On 6/8/06, Max [EMAIL PROTECTED] wrote: What they need is just to provide an access to their distinguisher in the form of blackbox. To prove its meaningfulness, the distinguisher must show consistent results in distinguishing AES-encrypted data (say, for a fixed plaintext without repeating blocks on their choice) from random data. I may be stepping into the crossfire here, but on my reading of their web page, they don't claim to be able to do that. They claim to be able to distinguish the low-order monomials formed by AES from a random function up to the PRF round count*. Perhaps it's my myopia, but that seems to be different than coming up with an actual distinguisher for real AES-encrypted data. It seems that the controversial assumption (that they are uninterested in debating) is that such non-randomness in the low-order monomials implies, is correlated with, is a good indicator of, a (potentially certificational) weakness. I'm curious what kind of algorithm might be used for coming up with the low-order monomials (indeed, this seems to be the main mystery, yes?). I think I can see how one could generate high-order ones (and reducing their order) by varying inputs in a black-box approach, but my math muscles are horribly developed, and the only way I can think of for generating them from lowest to highest order is to track changes in bit positions from round to round in forward operation, which seems to imply white-box instrumentation. Speculation welcome. [*] Given some suite of non-randomness checks that don't include anything tailored to the algorithm in question. -- Scientia Est Potentia -- Eppur Si Muove -- Admire the Artist's Handiwork Security guru for rent or hire - http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
On 5/17/06, Kuehn, Ulrich [EMAIL PROTECTED] wrote: Given known plaintext and corresponding ciphertext, there should not be too many keys that map the plaintext to the ciphertext. I don't have the probability at hand how many such 'collisions' you would expect from 256 random permutations, but intuitively I would not expect too many. However, I could be wrong here and would like to be corrected in this case. I'm a little rusty but I'll give it a shot. Well we have a byte x and a mapping f_k(x) = y, with f selected at random (for now I'll assume with replacement since 256 256!) from the set of all permutations, x and y from 0..255. The questions is what fraction of permutations have f_k(x) = y, I think the answer is 1/256. There's 255 other permutations, so the chance that there is at least one k' such that f_k'(x)=y is 255/256 = 99.6%. The chance that there is exactly one such k' is sampling with replacement and if I am not mistaken P(|K|=1) = (255/256)^255 = 0.36. Along those same lines, P(|K|=2) = (255/256)^253 * 254 / 256^2 = 0.001, so it looks like the expected number of equivocating keys is very small. I suspect that's why Terry Ritter's Dynamic Substitution algorithms, which are meant to replace XOR combiner in stream ciphers, maintain state. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
On 5/18/06, Travis H. [EMAIL PROTECTED] wrote: ... There's 255 other permutations, so the chance that there is at least one k' such that f_k'(x)=y is 255/256 = 99.6%. The chance that there is exactly one such k' is sampling with replacement and if I am not mistaken P(|K|=1) = (255/256)^255 = 0.36. Along those same lines, P(|K|=2) = (255/256)^253 * 254 / 256^2 = 0.001, so it looks like the expected number of equivocating keys is very small. Oops, I left off a term in the recurrence. P(|K|=2) = (255/256)^253 * ((254*255)/2)/(256^2) = 0.18 So the expected number of equivocating keys, given one byte of known plaintext, is a bit under two. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
anyone have New Hash Functions and their Use in Authentication and Set Equality
I've googled for New Hash Functions and their Use in Authentication and Set Equality and found several citations but no electronic copies. I don't have access to a library that might have it, does anyone here have one? Thanks. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: the meaning of linearity, was Re: picking a hash function to be encrypted
On 5/15/06, [EMAIL PROTECTED] [EMAIL PROTECTED] wrote: Other than post by a guy - Terry someone or another - on sci.crypt a number of years ago - I've never seen any work in this direction. Is there stuff I'm not aware of? That would probably be Terry Ritter, www.ciphersbyritter.com. He calls this function Dynamic Substitution: http://www.ciphersbyritter.com/#DynSubTech You could also probably use a Latin square: http://www.ciphersbyritter.com/#BBMTech -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
picking a hash function to be encrypted
So... Suppose I want a function to provide integrity and authentication, and that is to be combined with a stream cipher (as is the plaintext). I believe that authentication is free once I have integrity given the fact that the hash value is superencrypted using the stream cipher, whose key is shared by only the sender and recipient. I believe what I'm looking for is a strongly universal hash. I don't need much; everything I've seen is simultaneously too much and too little, often calling upon a block cipher, which seems redundant. What I was thinking of doing was using Poly1305, and using the stream cipher instead of AES. I think in this case that I can leave the MAC exposed, since it's a MAC and not a hash. Is there an analogous, hash function that does not use encryption internally? Backing up a bit, are there simpler hash functions (or families of functions) that could scale and, given the stream cipher, do the job? For example, the wikipedia entry for UMAC* shows a very simple hash family, which is trivial to scale to give a desired security level |D|. So I have a couple of questions about it; first, is it appropriate to use in this circumstance? Second, how would I authenticate variable-length messages; do I merely break them up into sequential pieces and authenticate each piece seperately, or is there a way to authenticate the whole thing without using some other hash function? [*] http://en.wikipedia.org/wiki/UMAC I'd really like to read the fine literature, but most of the papers I've found appear to predate the web. Any URLs would be much appreciated. And for reading this whole email, you get a present: http://dsns.csie.nctu.edu.tw/research/crypto/ -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: picking a hash function to be encrypted
On 5/14/06, Eric Rescorla [EMAIL PROTECTED] wrote: Consider the case where you're transmitting message M. The hash is H(M). You then encrypt (M || H(M)), generating K XOR (M || H(M)). If the attacker knows M and H, he can compute (M || H(M)) and compute K. Then he can re-encrypt a message M' of his choice. Excellent point. When I wrote that I had strongly universal hashes in mind, like UMAC, where the hash is chosen from a family of functions based on some secret data shared by sender and recipient. I mistakenly conflated them with ordinary hashes (which they are, once you pick one). Thanks for catching that. IMHO encrypting MACs is a good defensive measure, because you can then use a smaller hash value, so you end up encrypting as little as 4 bytes instead of transmitting 20 en clair, and now you also know the opponent hasn't learned anything. Does anyone know if MAC-then-encrypt(plaintext) versus encrypt(plaintext)-then-MAC makes a difference if the MAC itself is to be encrypted? I can't think of why it would. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: picking a hash function to be encrypted
On 5/14/06, Victor Duchovni [EMAIL PROTECTED] wrote: Security is fragile. Deviating from well understood primitives may be good research, but is not good engineering. Especially fragile are: Point taken. This is not for a production system, it's a research thing. TLS (available via OpenSSL) provides integrity and authentication, any reason to re-invent the wheel? It took multiple iterations of design improvements to get TLS right, even though it was designed by experts. IIUC, protocol design _should_ be easy, you just perform some finite-state analysis and verify that, assuming your primitives are ideal, no protocol-level operations break it. The 7th Usenix Security Symposium has a paper where the authors built up SSL 3.0 to find out what attack each datum was meant to prevent. They used mur-phi, which has been used for VLSI verification (i.e. large numbers of states). ATT published some code to do it too (called SPIN). It's effective if the set of attacks you're protecting against is finite and enumerable (for protocol design, I think it should be; reflection, replay, reorder, suppress, inject, etc.). I wouldn't consider fielding a protocol design without sanity-checking it using such a tool. Was there an attack against TLS which got past FSA, or did the experts not know about FSA? -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
the meaning of linearity, was Re: picking a hash function to be encrypted
- Stream ciphers (additive) This reminds me, when people talk about linearity with regard to a function, for example CRCs, exactly what sense of the word do they mean? I can understand f(x) = ax + b being linear, but how exactly does XOR get involved, and are there +-linear functions and xor-linear functions? Are they disjoint? etc. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: fyi: Deniable File System - Rubberhose
On 5/2/06, Ivan Krstic [EMAIL PROTECTED] wrote: I spent some time thinking about this a few years back: http://diswww.mit.edu/bloom-picayune/crypto/15520 Rubberhose was one of the things that came up, along with StegFS and BestCrypt. Unfortunately, it seems like Rubberhose hasn't seen work in over 5 years. Don't forget http://www.truecrypt.org/ The rubberhose web site disappeared a while back, but you can google and find an archive. I too have a mirror, should that one be out of date. I once ported a crypted file system, and indeed it is quite difficult with monolithic kernels. And you are really putting your data at risk, so be sure to include backups in your implementation. And test those backups, especially if you are backing up the crypted image, as opposed to encrypting your backups. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Intel microcode update encryption
http://microcodes.sourceforge.net/ There you can find a PDF reviewing the microcode update feature. Apparently the updates from Intel are 2048 bytes long overall, and have a 4-byte checksum, and are encrypted using some kind of mechanism on the processor. Since they don't (to my knowledge) express any instructions for doing encryption natively, they likely don't have any just for the microcode update, so it *should* be something simple, relying more on obscurity and the small size of the updates than cryptographic strength. Still, most of the details remain unknown to all but about ten guys in Intel. Writing your own jump to ring zero instruction is left as an exercise to the reader. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: PGP master keys
On 29 Apr 2006 02:00:18 -, StealthMonger [EMAIL PROTECTED] wrote: Interesting epilog: theregister has apparently now edited out all mention of master keys. They probably had their misunderstanding pointed out to them by countless people by now. But... did anyone else note the phrasing of the qualification Redmond ostensibly used? ``BitLocker has landed Redmond in some hot water over its insistence that there are no back doors for law enforcement.'' On first reading, one might assume they meant no back doors except for the overt corporate ADK, but that is not in fact what they said. Does anyone have any experience with disk or filesystem encryption, especially with regard to unclean shutdowns and power failures? Normal file systems are designed to fail in ways that are easy to clean up with fsck, but when you start to throw encryption into the mix, it seems like you can easily end up with something unrecoverable. Even without encryption I've seen apparent bugs in ext2fs on SMP machines that lead to sectors of nulls placed in files that were being written around the time the system crashed. Personally, I was playing with disk encryption on my system, shut down the system and something was holding file descriptors open... the system tried to kill everything three times, and then gave up and rebooted. As a consequence, I had my first unrecoverable data loss since I started keeping track (probably 1992 or so), since I had not backed up the data (the file system was too large for my backup device). Lesson learned! Now I do a nightly rsync to a partition that is only briefly mounted. Not as good as backup tapes, but it'll do for now. Are there any good solutions to the problem where a key isn't used frequently enough to stay in human memory, yet needs to be present in certain rare circumstances? Even with PGP keys... I've forgotten some of mine. Print it out and put it in a safety deposit box? I wonder if the typical corporate escrow key is exercised enough to avoid needing to write it down. IMHO interaction with human factors and imperfect hardware/software are understudied relative to their importance in actually having a functional robust real-world system. How complex can passwords be before users start to write them down? How many times does it take to memorize a passphrase? How frequently must one use it in order to retain it? -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: encrypted file system issues (was Re: PGP master keys)
On 5/1/06, Perry E. Metzger [EMAIL PROTECTED] wrote: Not if you design it correctly. Disk encryption systems like CGD work on the block level, and do not propagate CBC operations across blocks, So is it vulnerable to any of the attacks here? http://clemens.endorphin.org/LinuxHDEncSettings I used to run NetBSD 1.6 IIRC, and for some reason cgd was in previous and later releases but not that one. I found that puzzling. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
what's wrong with HMAC?
Ross Anderson once said cryptically, HMAC has a long story attched to it - the triumph of the theory community over common sense He wouldn't expand on that any more... does anyone have an idea of what he is referring to? -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Windows XP product activation, product keys, installation IDs, c.
In case you wondered what was behind those sequences of digits... Gory details here: http://www.licenturion.com/xp/fully-licensed-wpa.txt Ew, I think I have to take a shower now. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
non-cartesian A codes and latin squares
Background: An A-code is a matrix E x M, where e is the encoding rule used, and m is the message the transmitter should send (output). The message to be authenticated (input) is s in { s_1 .. s_k }, and the contents of the matrix are members of such that every row (encoding rule) contains s_1..s_k. In schemes with secrecy, there is an additional constraint that each column include each of s_1..s_k. Any unused cells are filled with 0, indicating that the message/encoding combination is invalid and indicative that the message is fraudulent. Put another way, if f : S x E - M is a map, then f is onto and for each encoding rule e, the map f(o , e) : S - M defined by s - f(s,e) is one-to-one. Furthermore, the code is minimal if |E| = |M|. As I understand it, this means there are no matrix elements containing 0. This is ostensibly desirable as it minimizes the number of bits necessary to encode the encoding rule (lg |E|). However, it would appear to provide no protection against substitution or impersonation. Question: Is that last statement correct? Isn't it the case that every minimal authentication code with secrecy is also a latin square? ...just wanted to be sure I was understanding it correctly... -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
non-cartesian A codes
Hi, does anyone have a web reference on how to construct matrices for non-cartesian A codes a la Simmons? I see descriptions of what they should look like, but no algorithms for creating them. -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
excellent wifi security page
http://www.drizzle.com/~aboba/IEEE/ -- Curiousity killed the cat, but for a while I was a suspect -- Steven Wright Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
is breaking RSA at least as hard as factoring or vice-versa?
So I'm reading up on unconditionally secure authentication in Simmon's Contemporary Cryptology, and he points out that with RSA, given d, you could calculate e (remember, this is authentication not encryption) if you could factor n, which relates the two. However, the implication is in the less useful direction; namely, that factoring n is at least as hard as breaking RSA. As of the books publication in 1992, it was not known whether the decryption of almost all ciphers for arbitrary exponents e is as hard as factoring. This is news to me! What's the current state of knowledge? -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Linux RNG paper
I have examined the LRNG paper and have a few comments. CC'd to the authors so mind the followups. 1) In the paper, he mentions that the state file could be altered by an attacker, and then he'd know the state when it first came up. Of course, if he could do that, he could simply install a trojan in the OS itself, so this is not really that much of a concern. If your hard drives might be altered by malicious parties, you should be using some kind of cryptographic integrity check on the contents before using them. This often comes for free when encrypting the contents. 2) His objection against using keyboard data is perhaps just an indication that reseeding of the pool should occur with sufficient entropy that the values cannot efficiently be guessed via brute force search and forward operation of the PRNG. If the reseeding is of insufficient to deter brute force input space search, other bad things can happen. For example, in the next paragraph the author mentions that random events may reseed the secondary pool directly if the primary pool is full. If an attacker were to learn the contents of the secondary pool, he could guess the incremental updates to its contents and compare results with the real PRNG, resulting in an incremental state-tracking attack breaking backward security until a reseed from the primary is generated (which appears to have a minimum of 8 bytes, also perhaps too low). The answer is more input, not less. It's annoying that the random number generator code calls the unpredictable stuff entropy. It's unpredictability that we're concerned with, and Shannon entropy is just an upper bound on the predictability. Unpredictability cannot be measured based on outputs of sources, it must be based on models of the source and attacker themselves. But we all know that. Maybe we should invent a term? Untropy? And now a random(3) tangent: While we're on the subject of randomness, I was hoping that random(3) used the old (TYPE_0) implementation by default... lots of DoS tools use it to fill spoofed packet fields, and one 32-bit output defines the entire state of the generator --- meaning that I could distinguish DoS packets which had at least 32 bits of state in them from other packets. However, it appears that Linux and BSD both use a TYPE_3 pool, which makes such simple techniques invalid, and would probably require identification of a packet stream, instead of testing packets one by one. Since use of a real pool has put it beyond my interest and perhaps my ability, I'm giving the idea away. Email me if you find a really good use for PRNG analysis of this sort. For a TYPE_0 generator, the equation is: i' = (i * 1103515245 + 12345) 0x7fff As far as low-hanging fruit goes, the higher generator types still never set the highest order bit (RAND_MAX is 0x7fff), and the outputs are unaltered pool contents. -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
passphrases with more than 160 bits of entropy
Hi, Does anyone have a good idea on how to OWF passphrases without reducing them to lower entropy counts? That is, I've seen systems which hash the passphrase then use a PRF to expand the result --- I don't want to do that. I want to have more than 160 bits of entropy involved. I was thinking that one could hash the first block, copy the intermediate state, finalize it, then continue the intermediate result with the next block, and finalize that. Is this safe? Is there a better alternative? -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
pipad, was Re: bounded storage model - why is R organized as 2-d array?
Anyone see a reason why the digits of Pi wouldn't form an excellent public large (infinite, actually) string of random bits? There's even an efficient digit-extraction (a/k/a random access to fractional bits) formula, conveniently base 16: http://mathworld.wolfram.com/BBPFormula.html I dub this pi pad. Is this idea transcendental or irrational? -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 [Moderator's note: I'd say irrational but I'll let other people chime in first. --Perry] - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
bulk quantum computation
Here's a 1997 paper on quantum computing in the large that I had been asking about: http://www.media.mit.edu/physics/projects/spins/home.html Neil Gershenfeld and Isaac Chuang have developed an entirely new approach to quantum computation that promises to solve many of these problems. Instead of carefully isolating a small number of qubits, we use a large thermal ensemble (such as a cup of coffee). Such a system has ~10^23 degrees of freedom; by applying RF pulses that excite nuclear magnetic resonances, we can create a tiny deviation from equilibrium that acts just like a much smaller number of pure qubits. -- Security Guru for Hire http://www.lightconsulting.com/~travis/ -- GPG fingerprint: 9D3F 395A DAC5 5CCC 9066 151D 0A6B 4098 0C55 1484 - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]