Re: [Barker, Elaine B.] NIST Publication Announcements
"James A. Donald" writes: >>> The Haber & Stornetta scheme provides a timestamping >>> service that doesn't require terribly much trust, >>> since hard to forge widely witnessed events delimit >>> particular sets of timestamps. The only issue is >>> getting sufficient granularity. > >> I don't know if their scheme was patented in Germany. >> It was in the U.S., though I think that at least some >> of the patents expire within the year. > > In looking this up, I have noticed a pile of patents > that patent something equivalent or near equivalent to a > patricia hash tree, or elaborately disguised patricia > trees, or something suspiciously similar to a patricia > hash tree, and various special cases of it, and > applications of it, without using the name "patricia > hash tree" Perhaps that's because this is a Merkle tree, not a patricia tree. Patricia trees are radix trees -- they're used for optimizing routing tables, not in cryptography. Perry - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: [Barker, Elaine B.] NIST Publication Announcements
>> The Haber & Stornetta scheme provides a timestamping >> service that doesn't require terribly much trust, >> since hard to forge widely witnessed events delimit >> particular sets of timestamps. The only issue is >> getting sufficient granularity. > I don't know if their scheme was patented in Germany. > It was in the U.S., though I think that at least some > of the patents expire within the year. In looking this up, I have noticed a pile of patents that patent something equivalent or near equivalent to a patricia hash tree, or elaborately disguised patricia trees, or something suspiciously similar to a patricia hash tree, and various special cases of it, and applications of it, without using the name "patricia hash tree" Since they seem reluctant to use the name "patricia hash tree" I suspect that there is already a pile of prior art, but I could not find any, though I am fairly sure the method is widely known. Also, wherever there is a pile of patents, there is usually a pile of prior art. Lest even more patents of the patricia hash tree be published, I would like to describe the method here, though it surely must be described somewhere else, probably long ago. Suppose we have a lot of records, each with a key that makes collision improbable or impossible, We assemble them in a patricia tree, with each node of the patricia tree containing a hash of its child nodes. The root of the patricia tree then, like a tiger hash, uniquely identifies the complete data set. If we have multiple copies of the data set, this data structure allows us to not only ensure that both copies are identical, but if there are small differences between them, such as recently added records, it allows us to efficiently find the differences, and thus efficiently bring the two data sets into agreement. It also allows us to prove that a given record was part of a particular data set at a particular time. Suppose the high order part of the key identifies the high order part of the time, followed by the id of the particular organization holding those records. The upper parts of the patricia hash tree are partially shared, peer to peer, similarly to file sharing with a tiger hash. Each participating organization keeps the nodes that relate to it. The lower parts are not shared except as needed. In this case, there will be a small set of top nodes of the tree that cease to change, because they only rely on keys earlier than a certain date, and this small and very slowly growing set of top nodes proves the complete state of the tree at all earlier dates. Then each organization can prove to all or any of the others that it had a particular record, or particular set of records, at a particular time, to the granularity of the time that is the high order part of the key. Where some or all of the data needs to be shared by some or all of the organizations, organizations can rapidly and efficiently identify any disagreements, and when they are in agreement, rapidly and efficiently prove to themselves, and to everyone else, and record for all time, that they are in agreement, since a small number of the topmost nodes of the tree proves the state of the tree at each and all times that contributed to those nodes. The structure serves for attestation and sharing, and since attestation usually involves sharing, and sharing attestation, the scope for patenting this structure over and over again in one disguise or another to be applied to one task or another that involves sharing and or attestation is limited only by the boundless imagination of patent lawyers. One can also add horizontal and backwards hash relationships between nodes that serve little practical purpose other than allowing one to have a single rapidly changing node node attesting instead of a small set of nodes, and allowing it to be nominally something other than a patricia hash tree. Thus, for example, instead of using forty or so nodes to attest for the state of million organizations over a billion time periods, one can use a hash of those forty nodes, and there are no end of different ways one can hash those forty or so nodes together. But under that hash, it is still a patricia hash tree doing the actual work of gluing the data together. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Merry Certmas! CN=*\x00thoughtcrime.noisebridge.net
On Tue, Sep 29, 2009 at 10:51:33PM -0700, Jacob Appelbaum wrote: > It's been long enough that everyone should be patched for this awesome > class of bugs. This certificate and corresponding private key should > help people test fairly obscure software or software they've written > themselves. I hope this release will help with confirmation of the bug > and with regression testing. Feel free to use this certificate for > anything relating to free software too. Consider it released into the > public domain of interesting integers. If anyone is curious about the impact of this on the Postfix TLS engine (March 2006, version 2.3.0 and later releases): 1. Postfix checks subject domains obtained from either subjectAltName or CN to ensure that the ASN.1 string object length is equal to the C string length. Certificates that fail this test are considered anonymous. These checks were added in the Spring of 2005 when the contributed TLS patch adopted in the 2.2 release was significantly extended and revised. 2. Postfix only matches *.example.com certificates against single-label sub-domains of example.com. Thus for example, the Postini wild-card certificate for: *.psmtp.com does not match (say Verisign's), MX records of the form: verisign.com. IN MX 100 verisign.com.s6a1.psmtp.com. verisign.com. IN MX 200 verisign.com.s6a2.psmtp.com. verisign.com. IN MX 300 verisign.com.s6b1.psmtp.com. verisign.com. IN MX 400 verisign.com.s6b2.psmtp.com. (Postfix also does not, for "secure-channel" destinations, trust DNS enough to let MX records influence the name expected in a peer certificate. So Postini's wildcard certificate is perhaps only useful with other sending systems). So a "*" certificate will never match any peer domain. Bottom line, this issue does not impact the Postfix secure-channel TLS use case. -- Viktor. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: SHA-1 and Git (was Re: [tahoe-dev] Tahoe-LAFS key management, part 2: Tahoe-LAFS is like encrypted git)
On Sun, Sep 27, 2009 at 02:23:16PM -0700, Fuzzy Hoodie-Monster wrote: > As usual, I tend to agree with Peter. Consider the time scale and > severity of problems with cryptographic algorithms vs. the time scale > of protocol development vs. the time scale of bug creation > attributable to complex designs. Let's make up some fake numbers, > shall we? (After all, we're software engineers. Real numbers are for > real engineers! Bah!) > > [snip] > > Although the numbers are fake, perhaps the orders of magnitude are > close enough to make the point. Which is: your software will fail for > reasons unrelated to cryptographic algorithm problems long before > SHA-256 is broken enough to matter. Perhaps pluggability is a source > of frequent failures, designed to solve for infrequent and > low-severity algorithm failures. I would worry about an overfull \hbox > (badness 1!) long before I worried about AES-128 in CBC mode with > a unique IV made from /dev/urandom. Between now and the time our "AES-128 in CBC mode with a unique IV made from /dev/urandom" is manifestly not the issue of the day. The issue is hash function strength. So when would you worry about MD5? SHA-1? By your own admission MD5 has already been fatally wounded and SHA-1 is headed that way. > ciphers and hashes and signatures are broken, we'll have a decade to > design and implement the next simple system to replace our current > system. Most software developers would be overjoyed to have a full > decade. Why are we whining? We don't have a decade to replace MD5. We've had a long time to replace MD5, and even SHA-1 already, but we haven't done it yet. The reason is simple: there's more to it than you've stated. Specifically, for example, you ignored protocol update development (you assumed 1 new protocol per-year, but this says nothing about how long it takes to, say, update TLS) and deployment issues completely, and you supposed that software development happens at a consistent, fast clip throughout. Software development and deployment are usually constrained by legacy and customer behavior, as well as resource availability, all of which varies enormously. Protocol upgrade development, for example, is harder than you might think (I'm guessing though, since you didn't address that issue). Complexity exists outside protocol. This is why we must plan ahead and make reasonable trade-offs. Devising protocols that make upgrade easier is important, supposing that they actually help with the deployment issues (cue your argument that they do not). I'm OK with making up numbers for the sake of argument. But you have to make up all the relevent numbers. Then we can plug in real data where we have it, argue about the other numbers, ... > What if TLS v1.1 (2006) specified that the only ciphersuite was RSA > with >= 1024-bit keys, HMAC_SHA256, and AES-128 in CBC mode. How > likely is it that attackers will be able to reliably and economically > attack those algorithms in 2016? Meanwhile, the comically complex > X.509 is already a punching bag > (http://www.blackhat.com/presentations/bh-dc-09/Marlinspike/BlackHat-DC-09-Marlinspike-Defeating-SSL.pdf > and > http://www.blackhat.com/presentations/bh-usa-09/MARLINSPIKE/BHUSA09-Marlinspike-DefeatSSL-SLIDES.pdf, > including the remote exploit in the certificate handling code itself). We don't have crystal balls. We don't really know what's in store for AES, for example. Conservative design says we should have a way to deploy alternatives in a reasonably short period of time. You and Peter are clearly biased against TLS 1.2 specifically, and algorithm negotiation generally. It's also clear that you're outside the IETF consensus on both matters _for now_. IMO you'll need to make better arguments, or wait enough time to be proven right by events, in order to change that consensus. Nico -- - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Re: Unexpected side-effects
Jerry Leichter wrote: > Well, here I'll expect one. :-) Not a new idea, although I don't know where I heard it the first time. > As there is increasing pressure to keep > records of Internet use, there will be a counter-move to use VPN's which > promise to keep no records. Which will lead to legal orders that > records be kept, with no notification to those being tracked. Enter > secure remote attestation - rendering it impossible for an appropriately > defined non-logging implementation to start logging without giving this > fact away. Probably off-topic for this list, but this doesn't make much sense to me, as such non-logging implementations likely will be just as illegal as notifying the client of the change, which seems an overall better solution if you are willing to break the law (provided you can hide the notification from authorities). [In Germany, means of surveillance are required by law, as is record keeping]. Getting back on topic, cryptographically speaking, it's also quite possible to just monitor all ingoing and outcoming traffic and correlate one with the other. Preventing this is not easy, even if encryption is used. > Maybe it'll be the pirates who make the first large-scale use of those > TPM's! Maybe, and this would be a major confirmation that TPM actually works at any non-trivial scale. I can't see it, though. Thanks, Marcus - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
[Paul F. Doyle] Timestamping
Forwarded message: From: "Paul F. Doyle" To: , Cc: Subject: Re: [Barker, Elaine B.] NIST Publication Announcements Date: Wed, 30 Sep 2009 09:55:36 -0400 Hello Perry and Stephan (cc: Dan Geer), Dan Geer forwarded a message thread from the crypto mailing list. There is an approach to Trusted Time Stamping you may find interesting, useful and rather different given the circumstances you've described in the thread. It is known as the Transient Key Method and is NOT based on a conventional PKI method for generating cryptographic time stamps, but instead a fully distributed, web-style, self-validating model. I would be happy to describe the Transient Key Method in detail if this would be helpful and can forward along some background documentation if you are interested. BTW, it is one of the methods included in the American National Standard X9.95. Please let me know how I can be of assistance. Thanks, --Paul "A life without integrity is meaningless... ...a record or dataset without integrity is worthless!" Paul F. Doyle Founder & CEO Proofspace P.O. Box 369 Ada, MI 49301 v. 616-458-5733 m. 616-292-8350 f. 866-685-2386/616-458-2271 www.proofspace.com LinkedIn: www.linkedin.com/in/paulfdoyle e. p...@proofspace.com skype. paul_proofspace - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Merry Certmas! CN=*\x00thoughtcrime.noisebridge.net
Hello *, In the spirit of giving and sharing, I felt it would be nice to enable other Noisebridgers (and friends of Noisebridge) to play around with bugs in SSL/TLS. Moxie was just over and we'd discussed releasing this certificate for some time. He's already released a few certificates and I thought I'd join him. In celebration of his visit to San Francisco, I wanted to release fun-times-at-moxie-marlinspike-high. This is a text file that contains a fully valid, signed certificate (with private key) that can be used to exploit the NULL certificate prefix bug[0]. The certificate is valid for * on the internet (when exploiting libnss software). The certificate is good for two years. It won't work for exploiting the bug for software written with the WIN32 api, they don't accept (for good reason) *! I suggest the use of Moxie's sslsniff[1] if you're so inclined to try network related testing. It may also be useful for testing code signing software. It's been long enough that everyone should be patched for this awesome class of bugs. This certificate and corresponding private key should help people test fairly obscure software or software they've written themselves. I hope this release will help with confirmation of the bug and with regression testing. Feel free to use this certificate for anything relating to free software too. Consider it released into the public domain of interesting integers. Enjoy! Best, Jacob [0] http://thoughtcrime.org/papers/null-prefix-attacks.pdf [1] http://thoughtcrime.org/software/sslsniff/ Private-Key: (1024 bit) modulus: 00:cf:4d:17:42:00:8d:0c:41:95:31:8c:40:30:bc: 5e:42:b6:28:09:75:2f:19:61:d9:ab:4d:ec:f3:44: c4:1c:01:95:6f:27:eb:70:07:98:4f:1e:05:d0:f3: 6c:49:45:e6:de:48:7a:59:f0:c2:93:6a:37:9c:02: 72:4f:bd:14:36:26:a1:70:97:d4:fe:4b:24:e8:cd: 29:1e:61:1a:85:b0:6f:96:06:83:10:13:d6:89:9f: bd:07:67:f1:42:de:9b:63:67:8b:96:f9:06:ef:7c: 93:4b:6a:f9:39:31:32:7f:98:59:ef:ce:91:be:05: ce:f0:82:33:d8:76:06:4c:9f publicExponent: 65537 (0x10001) privateExponent: 00:8c:4f:3b:7c:ba:ee:bc:ea:ee:d6:58:7d:61:ff: 3d:35:9e:21:3f:35:87:a9:80:67:59:e1:26:8e:09: 6f:4b:1d:6f:4d:8b:11:7a:04:49:fc:d2:ef:50:dc: 51:e0:ce:65:52:f2:6f:8d:cc:bd:86:15:90:8a:11: c5:d9:5e:ba:fc:2b:fc:e3:a0:cd:c8:f0:9a:05:76: 06:82:07:a9:bd:14:cc:c7:7e:54:b9:32:5b:40:7a: 35:0a:26:80:d7:30:98:d6:b7:71:d5:9d:f4:0d:f2: 28:b5:a9:0c:2e:6d:78:19:86:a9:31:b0:a1:43:1c: 57:2c:78:a9:42:b2:49:d8:71 prime1: 00:ec:07:79:1d:e2:50:14:77:af:99:18:1b:14:d4: 0c:25:0c:20:26:0d:dd:c7:75:0e:08:d3:77:72:ce: 2d:57:80:9d:18:bb:60:7b:b2:62:4e:21:a1:e6:84: 96:91:31:15:cc:5b:89:5b:5a:83:07:96:51:e4:d4: e6:3a:40:99:03 prime2: 00:e0:d7:5a:07:0e:cc:a6:17:22:f8:ec:51:b1:7b: 17:af:3a:87:7b:f1:e4:6d:40:48:28:d2:c0:9c:93: e0:f1:8f:79:07:8f:00:e0:49:1d:0e:8c:65:41:ba: c8:20:e2:ae:78:54:75:6b:f0:41:e5:d1:9c:2e:23: 49:79:53:35:35 exponent1: 15:17:15:db:75:bd:72:16:bf:ba:0e:4d:5d:2f:15: 66:ba:0e:a5:57:d7:d9:5a:bc:46:4d:9e:fe:c3:2d: 8a:04:14:05:81:b8:bd:54:d3:33:e8:0d:6f:6b:a9: 88:8f:ba:42:e8:6a:fd:9e:b8:d6:94:b7:fc:9a:89: 77:eb:0d:c1 exponent2: 5c:5a:38:61:63:c3:cd:88:fd:55:6f:84:12:b9:73: be:06:f5:75:84:a3:05:f8:fc:6a:c0:3e:5b:52:26: 78:32:2d:4d:5c:80:c8:9f:5f:6f:05:5d:e6:04:b9: 85:40:76:d7:78:21:8f:07:6d:99:df:62:1e:55:62: 2d:92:6e:ed coefficient: 00:c5:62:ea:ee:85:5c:eb:e6:07:12:58:a5:63:5a: 8f:e3:b3:df:c5:1e:cc:01:cd:87:d4:12:3f:45:8e: a9:4c:83:51:31:5a:e5:8d:11:a1:e3:84:b8:b4:e1: 12:33:eb:2d:4c:4e:8c:49:e2:0d:50:aa:ca:38:e3: e6:c2:29:86:17 Certificate Request: Data: Version: 0 (0x0) Subject: C=US, CN=*\x00thoughtcrime.noisebridge.net, ST=California, L=San Francisco, O=Noisebridge, OU=Moxie Marlinspike Fan Club Subject Public Key Info: Public Key Algorithm: rsaEncryption RSA Public Key: (1024 bit) Modulus (1024 bit): 00:cf:4d:17:42:00:8d:0c:41:95:31:8c:40:30:bc: 5e:42:b6:28:09:75:2f:19:61:d9:ab:4d:ec:f3:44: c4:1c:01:95:6f:27:eb:70:07:98:4f:1e:05:d0:f3: 6c:49:45:e6:de:48:7a:59:f0:c2:93:6a:37:9c:02: 72:4f:bd:14:36:26:a1:70:97:d4:fe:4b:24:e8:cd: 29:1e:61:1a:85:b0:6f:96:06:83:10:13:d6:89:9f: bd:07:67:f1:42:de:9b:63:67:8b:96:f9:06:ef:7c: 93:4b:6a:f9:39:31:32:7f:98:59:ef:ce:91:be:05: ce:f0:82:33:d8:76:06:4c:9f Exponent: 65537 (0x10001) Attributes: a0:00 Signature Algorithm: md5WithRSAEncryption 64:e6:b2:77:45:74:c3:dc:f6:3d:e7:73:7f:0f:fb:dd:d7:30: c3:0f:30:d5:52:2c:6b:41:ad:40:2b:4b:07:2a:de:80:69:d4: a7:0b:6f:ed:cc:62:e7:4d:e1:fc:1e:81:0d:94:b9:c8:9b:14: 0a:10:d4:8e:f9:53:76:11:51:1d:c9:80:ca:15:e5:78:02:e1: d1:89:95:b5:4a:3f:e0:f7:f3:35:ad:1f:7d:85:5b:8c:f5:de:
Re: [Barker, Elaine B.] NIST Publication Announcements
On Sep 29, 2009, at 10:31 AM, Perry E. Metzger wrote: Stephan Neuhaus writes: For business reasons, Alice can't force Bob to use a particular TTA, and it's also impossible to stipulate a particular TTA as part of the job description (the reason is that Alice and the Bobsgreat band name BTW---won't agree to trust any particular TTA and also don't want to operate their own). You don't need such a complicated description -- you're just asking "can I do secure timestamping without requiring significant trust in the timestamping authority." The Haber & Stornetta scheme provides a timestamping service that doesn't require terribly much trust, since hard to forge widely witnessed events delimit particular sets of timestamps. The only issue is getting sufficient granularity. I don't know if their scheme was patented in Germany. It was in the U.S., though I think that at least some of the patents expire within the year. --Steve Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com