Re: Fwd: Tor security advisory: DH handshake flaw
Ben Laurie writes: > Apologies, slightly at cross-purposes here. For a start, Sophie Germain > primes are needed for D-H (or rather, safe primes), and secondly, I was > talking about proving arbitrary primes, rather than constructing > provable primes. Dan Bernstein has lots of good information on the state of the art in general primality (and compositeness) proving. http://cr.yp.to/primetests.html points to his recent survey paper and has a table of the various algorithms. Interestingly there are considerable tradeoffs between proving time and verification time. There are some methods that create "instant" proofs but then take a long time to verify. http://cr.yp.to/ntheory.html has some of Dan's own work, including an algorithm which creates a certificate in time quadratic in length, with verification costing time proportional to the 4th power of the length. He suggests that at this point the best practical algorithm is based on elliptic curves, which is conjectured to have running time proportional to the 4th power of length for finding proofs and to the 3rd power for verifying them. I don't know what the actual numbers are for prime sizes of interest (presumably 1K-8K bits or so). References are available from his papers. Several programs to implement ECPP can be found from http://primes.utm.edu/links/programs/seeking_large_primes/. I don't know about source code however. It might be interesting to run these over some of the Oakley primes and publish the certs - I vaguely recall seeing something like that in an RFC. Hal - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
herding attack paper submitted to ePrint archive
Guys, Yoshi and I have submitted a draft of the Herding Hash Functions paper up on the IACR ePrint server, and assuming there are no problems, it should be up reasonably soon. The core of the result is that when I can find lots of collisions for a hash function by brute force (or maybe analytically, though that gets more complicated), I can also break most systems that use a hash function to prove prior knowledge. I gave a rump session talk on this a few days ago at Crypto. --John Kelsey, NIST, August 2005 - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
[Clips] [MTNews] CRYPTO-Server 6.3
--- begin forwarded text Delivered-To: [EMAIL PROTECTED] Date: Mon, 22 Aug 2005 15:57:56 -0400 To: "Philodox Clips List" <[EMAIL PROTECTED]> From: "R.A. Hettinga" <[EMAIL PROTECTED]> Subject: [Clips] [MTNews] CRYPTO-Server 6.3 Reply-To: [EMAIL PROTECTED] Sender: [EMAIL PROTECTED] --- begin forwarded text Date: Mon, 22 Aug 2005 12:47:49 -0700 To: [EMAIL PROTECTED] From: MacTech News Moderator <[EMAIL PROTECTED]> Subject: [MTNews] CRYPTO-Server 6.3 Sender: <[EMAIL PROTECTED]> This message comes to you from MacTech News -- the Mac(tm) OS Technical News and Info server. See below for more info on this list (including sub/unsub details). __ CRYPTOCard LAUNCHES CRYPTO-Server 6.3 FOR MAC OS X TO MAKE IT SIMPLE FOR "TIGER" USERS TO GAIN TWO-FACTOR ATM-STYLE AUTHENTICATED ACCESS TO DESKTOPS, LAPTOPS, AND APACHE WEB SERVER CRYPTO-Server 6.3 for OS X provides "Tiger" Users With Simple Authenticated Access To Desktops-Even If They Are Not Connected To The Network CRYPTOCard (http://www.cryptocard.com/), a leading authentication developer, today launched CRYPTO-Server 6.3 for OS X, the authentication solution designed to make it simple to positively identify all Tiger users attempting LAN, VPN (Apple or Cisco), or Web-based (Apache) access. Specifically designed to fully integrate with Tiger's newly-developed support for smart card environments, CRYPTO-Server 6.3 couples something in the user's possession (a multi-function smart card, USB token, hardware token, or software token), with something the user knows (their PIN) to provide secure, enterprise-class LAN, Web, and remote ATM-style One-PIN-and-Youre-In authenticated access that mirrors the look and feel of the OS X logon ensuring that the technology is simple for Tiger users to utilize. CRYPTO-Server 6.3's "Fast User Switching" functionality also makes it simple for multiple Tiger users to securely access the Mac, using smart cards or tokens in a stand-alone or networked environment. "Understanding that an organization cannot guarantee a system security if it cannot positively authenticate each individual user, CRYPTOCard has developed a fully-integrated authentication solution specifically designed for Tiger," commented Malcolm MacTaggart, President & CEO, CRYPTOCard Corporation. "CRYPTO-Server 6.3 now makes it simple for Tiger users, particularly in the traditional Mac strongholds of the health, legal, higher education, and printing/publishing/multimedia sectors, to provide true ATM-style One-PIN-and-Youre-In enterprise-class strong user authentication for LAN, VPN, Web, or remote system access," MacTaggart continued. "To meet the needs of U.S Federal customers, CRYPTOCard's Smart Card readers support the U.S Federal Smart Cards (CAC & PIV) and the drivers are pre-installed in Tiger." "The breakthrough features in Mac OS X Tiger are enabling innovation across a diverse range of developers and markets," said Ron Okamoto, Apple's vice president of Worldwide Developer Relations. "Were thrilled that CRYPTOCard is taking advantage of Tiger to deliver easy-to-use enterprise class authentication solutions." Incorporating CRYPTOCard's familiar ATM-style logon, that has proven to eliminate the user resistance usually encountered when organizations attempt to implement an additional layer of security, CRYPTO-Server 6.3 for OS X generates a one-time password for every log-on attempt, making stolen credentials useless to hackers while simultaneously ensuring Tiger users do not have to memorize complicated credentials significantly reducing the help-desk costs associated with resetting forgotten passwords, and the obvious security risk resulting from users writing down their passwords. CRYPTO-Server's remote access functionality offers support for Apple's VPN Server, with the same "One-PIN-and-Youre-In." experience, however, if hardware tokens are employed, no additional software is required on the client side CRYPTOCard's two-factor-authentication is ready to go, "out-of-the-box." CRYPTO-Server 6.3's CRYPTO-Web component also makes it simple for Tiger users to utilize the exact same ATM-style log-on protocol to positively authenticate themselves to Apache and IIS Websites, right down to the page level. And, with almost 75 percent (or more than 13 million) of the world's web servers running on Apache, CRYPTO-Server 6.3 for OS X represents a significant advance in authentication technology for the web medium. CRYPTO-Server 6.3 for OS X provides administrators with centralized authentication and management capability, emphasizing ease-of-use and tight integration with Apple's Open Directory LDAP services. CRYPTO-Server 6.3 will not only make it simple to enforce two-factor authentication as the only way to access a workstation, but will also make it simple to lock down access th
Re: online MD5 crack database
I should (apparently) add that at the time I did not know enough to ask relevant questions, but it was tossed off in such a way as to sound like that if I did know anything I'd realize the speaker was telling me something obvious so since it didn't seem obvious to me then I must not know anything. Hadn't thought about it since until I saw Perry's post. [ Imagine the math professor who having said "It is obvious that..." steps back from the board for two full minutes before continuing "... yes, it is obvious that..." and you have the feel for the setting two decades ago when I heard the claim. ] --dan - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: online MD5 crack database
On 8/22/05, Steven M. Bellovin <[EMAIL PROTECTED]> wrote: > In message <[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes > : > > > >...the folks at Fort Meade had every > >possible BSD password indexed by its /etc/passwd > >representation. > I'm sorry, I flat-out don't believe that. Probably some details were left out in the telling. Such as "all possible alphanumeric passwords of length 1-16 characters". -- There are no bad teachers, only defective children. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: online MD5 crack database
On Mon, Aug 22, 2005 at 10:08:29AM -0400, Steven M. Bellovin wrote: > >In 1985 I was told by an MIT professor with DoD > >connections and a clearance that certainly no > >later than 1979 the folks at Fort Meade had every > >possible BSD password indexed by its /etc/passwd > >representation. Reversing a password meant to > >simply look up the /etc/password text on-disk to > >see what tape it was on and to then read that > >tape. > > > > I'm sorry, I flat-out don't believe that. For one thing, why would > that have been necessary in 1979? Unix just wasn't that important. > For another, let's do some arithmetic. > More plausible perhaps if they had used a space/time tradeoff, to make the space manageable, then the question is whether CPUs were fast enough or character set sufficiently restricted to make the pre-computation feasible. -- /"\ ASCII RIBBON NOTICE: If received in error, \ / CAMPAIGN Victor Duchovni please destroy and notify X AGAINST IT Security, sender. Sender does not waive / \ HTML MAILMorgan Stanley confidentiality or privilege, and use is prohibited. - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: online MD5 crack database
In message <[EMAIL PROTECTED]>, [EMAIL PROTECTED] writes : > >In 1985 I was told by an MIT professor with DoD >connections and a clearance that certainly no >later than 1979 the folks at Fort Meade had every >possible BSD password indexed by its /etc/passwd >representation. Reversing a password meant to >simply look up the /etc/password text on-disk to >see what tape it was on and to then read that >tape. > I'm sorry, I flat-out don't believe that. For one thing, why would that have been necessary in 1979? Unix just wasn't that important. For another, let's do some arithmetic. First -- I'm assuming you mean the classic Morris and Thompson scheme, which has salts. (That scheme was only published in 1979, but maybe Morris told people -- and NSA had tracked and used Unix from way back.) Assume there are 100 possible characters -- the 95 printable, plus a handful of control characters. In those days, @ and # were line kill and character erase, but that meant that ^U and ^H were available. At 8 characters max, that gives us 100^8 possible passwords, times 4K salts. That's about 4*10^19. I'll neglect the indexing overhead, though it would be considerable. Now, the largest disk drive I know of today is about 400GB, or 4*10^11. That means you'd need 10^8 drives. At, say, $50/drive -- very cheap, because you need to factor in the controller and CPU overhead -- that's $5*10^9. Even by NSA's standards, that's a hefty chunk of change. You did, however, mention tapes. The tape drives of that era were, if I recall correctly, 9-track, 6250 bits/inch, with the largest reels being 2400'. Assuming no interrecord gaps -- and such gaps were mandatory and consumed a noticeable amount of space -- that translates to 2400*12*6250 bytes/real, or 180*10^6. If my arithmetic is right, that translates to 222 *billion* tapes. Sorry; even Fort Meade isn't that big. Oops -- I forgot that each password is 8 bytes. Multiply all of those numbers by 8... To figure out how long it would take to generate them, we should start with Diffie and Hellman's DES-cracker. Yes, the set of passwords is smaller than the set of DES keys, but not by that much if you reall allow "every possible" password. Besides, these passwords were (a) iterated 25 times, i.e., having a 25x slowdown, and (b) required custom chips because of the salt. And all this for a system that wasn't in widespread use? Now -- if you mean old-style passwords, of the type Morris and Thompson replaced, it becomes somewhat more plausible. Let's restrict ourselves to 64 characters, mirroring the password styles of the day, unsalted. That's 64^8. It still comes to 1.5 million reels of tape, however, so I still don't believe it. --Steven M. Bellovin, http://www.cs.columbia.edu/~smb - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: Fwd: Tor security advisory: DH handshake flaw
Jerrold Leichter wrote: | Apologies, slightly at cross-purposes here. For a start, Sophie Germain primes | are needed for D-H (or rather, safe primes), and secondly, I was talking about | proving arbitrary primes, rather than constructing provable primes. > Isn't *proving* primality rather overkill for the purpose at hand (which seems to be verifying that an alleged prime isn't a non-prime, sent to "spike" the system). Are there any known sets of numbers - much less ways to *choose* members of those sets - which will show up as prime with significant probability to Miller-Rabin? As far as I know, M-R has a *worst case* false positive rate of 1/4. Even a fairly small number of random M-R tests should make slipping in a non-prime less probable than a variety of other attacks. There aren't any such sets known to me. Can I be sure there are none known to anyone? No. Not sure I agree with the false positive rate. What is known is that 3/4 of the bases are strong witnesses for a composite number. But is it known that these are evenly distributed? I don't know, but that would be required for a 1/4 false positive rate. If you want to go further, there's the Baille-PSW test (http://mathworld.wolfram.com/Baillie-PSWPrimalityTest.html) which it appears has no "false positives" for any integer of less than about 10,000 digits - way beyond what you would likely use in the near future. Based on a statistical argument from a closed source prover and verifier. Hmm. The point of proofs (at least, useful proofs) is that they produce certificates that are cheap to verify. So, yeah, sure it may be overkill, but I'll do the killing so you don't have to. Cheers, Ben. -- http://www.apache-ssl.org/ben.html http://www.thebunker.net/ "There is no limit to what a man can do or how far he can go if he doesn't mind who gets the credit." - Robert Woodruff - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
Re: online MD5 crack database
"Perry E. Metzger" writes: | | This website has a large database of MD5 hashes of common passwords: | | http://gdataonline.com/ | | Presumably, as storage continues to get cheaper, this sort of thing | will only become easier. | .. | None of this is new -- I'm just noting that the trend continues apace. | In 1985 I was told by an MIT professor with DoD connections and a clearance that certainly no later than 1979 the folks at Fort Meade had every possible BSD password indexed by its /etc/passwd representation. Reversing a password meant to simply look up the /etc/password text on-disk to see what tape it was on and to then read that tape. --dan - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]
online MD5 crack database
This website has a large database of MD5 hashes of common passwords: http://gdataonline.com/ Presumably, as storage continues to get cheaper, this sort of thing will only become easier. Ways to ameliorate it? Consistently using long (64 bits or more) salts with hashed passwords makes storing such databases much harder, and encouraging the use of far longer passphrases with much more entropy reduces the problem further. Longer hashes are also a good idea. None of this is new -- I'm just noting that the trend continues apace. Perry PS I found the link off of a /. story earlier today - The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]