Cryptol, Language of Cryptography, Now Available To the Public 140
solweil writes to mention that Cryptol, a 'domain specific language for the design, implementation and verification of cryptographic algorithms,' is now available to the public. Cryptol was originally designed for the NSA. It allows for a quick evaluation and continued revisions, and is available for Linux, OS X, and Windows.
Crack this! (Score:2, Funny)
41R5T 3N6RI27ED P057 !
Re: (Score:1, Funny)
L053r
Re: (Score:2)
Re: (Score:3, Funny)
Re: (Score:2)
Re: (Score:2)
More like cryptLOL, amirite?
Re: (Score:2)
41R5T 3N6RI27ED P057
Airst Engrrted Post? Yup, that's definitely a good encryption scheme.
Re: (Score:2)
Kudos to NSA (Score:5, Interesting)
Re: (Score:1, Funny)
So, how DO you factor large semiprimes fast?
Re:Kudos to NSA (Score:5, Funny)
Re: (Score:2, Funny)
Re: (Score:2, Funny)
Re: (Score:2, Funny)
So, how DO you factor large semiprimes fast?
can someone explain why this is hard to do? It seems like a straghtforward process since the number of primes is essentially fixed. (there are quite a few of them but we keep hearing announcements about a new ONE being found, so there can't be that many of them that are known, someone's got a book I'm sure)
Just a matter of looping through all known primes, seeing if x divides by it. That's order 1 since the number of primes is "fixed". If you don't find anythin
Re:Kudos to NSA (Score:5, Informative)
There are infinitely many prime numbers. [wikipedia.org]
Re:Kudos to NSA (Score:4, Funny)
There are infinitely many prime numbers. [wikipedia.org]
The GP said the number of primes is essentially fixed which is consistent with the number of primes being infinite, I suppose.
Re: (Score:1, Informative)
That's from the definition of a prime number. Take any natural number N. Either (1) N is prime, or (2) N is divisible by a prime number (it's not prime, i.e. it's composite: the product of two or more prime numbers).
Euclid is using this fact to show that the original finite set does not contain all primes, because either that original set did not contain N, or it did not contain a prime factor of N. Hence, no matter how many primes you find, there will always be more primes.
Re: (Score:1)
It follows from the prime decomposition theorem -- that every number is a product of primes. (Or, more-or-less equivalently, Euclid's algorithm)
The proof is essentially a "counting proof". Collect any finite list of primes, and one can construct a number that is not divisble by any of them.
For example, if p_1 ... p_n are prime, N = (p_1 x ... x p_n) + 1 isn't divisble by any of them. Which means that it is prime, or there is a prime number (that isn't in the list) that does divide your new number N.
Re: (Score:3, Insightful)
Start with a small set to see the logic if you need to.
Say just (2, 3, and 5). All prime numbers.
Now the product of 2, 3, and 5 is 30. Add 1 to this and you get 31.
31 is not divisable by 2. The closest you can get to 31 in mulitples of two is 30 (which is 3 times 5 times... you guessed it 2.) and you have 1 left over.
31 is not divisable by 3. It's the same as 2. The closest you get is 30 (2 times 5 times... 3!) and you have 1 left over.
The same goes for 5. Because you are adding 1 to the product of all thre
Re: (Score:2)
This is going to be the same for any group of prime numbers you pick.
Counter-example: I pick 3 and 5. 3x5+1 is 16 which is not prime. The demonstration is only valid is you pick all the first N prime numbers.
No, that's covered in the proof: "... or there is a prime number or prime numbers which the resultant number could be decomposed into but are not in the original finite set of primes." The resultant number (16) is divisible by a prime that is not in your set (2). Therefore there are more primes than are in your set.
Re: (Score:2)
This is going to be the same for any group of prime numbers you pick.
Counter-example: I pick 3 and 5. 3x5+1 is 16 which is not prime. The demonstration is only valid is you pick all the first N prime numbers.
Read the post again:
31 therefore is either a prime number itself, or it can be broken down into a product of prime numbers.
But we've shown that the prime numbers in our list can't be the primes that do that, since none of them can divide into our result cleanly.
So, 16 is either a prime number itself, or it can be broken down into a product of prime numbers, and the the prime numbers in your list can't be the primes that do that. In particular, the prime you are looking for is 2.
Re: (Score:2)
Re:Kudos to NSA (Score:4, Interesting)
The RSA problem is defined as the task of taking eth roots modulo a composite n: recovering a value m such that c=me mod n, where (n, e) is an RSA public key and c is an RSA ciphertext.
Keep in mind these are typically 1024-bit (or more) numbers -- 2 ^ 1024 possible numbers to factor. Also, the world's record for factorization at the moment is for factoring a 668-bit number that took "several months of computer time using the combined power of 80 AMD Opteron CPUs. [wikipedia.org]"
Re: (Score:2, Informative)
Re: (Score:3, Informative)
It's not so hard to factor a 32-bit number with a 64-bit computer. It is very hard to efficiently factor a 2048-bit number with a 64-bit computer. Even if you had a list of all prime numbers that can be expressed in 2k or fewer bits, streaming all that data to your CPU would take a lot of bandwidth.
Re: (Score:2)
It's not so hard to factor a 32-bit number with a 64-bit computer. It is very hard to efficiently factor a 2048-bit number with a 64-bit computer.
Hmm, that raises the question... has anyone tried to build a 2048-bit computer?
Sounds like it might be fun project for the right TLA with a multi-billion dollar budget...
Re: (Score:2)
I don't think that a 2kbit architecture would be particularly useful. Sure, it might work well for factoring large numbers, but for many other cryptography-related tasks, the lack of granularity would make it rather inefficient. If you're going to build a computer for factoring large numbers, you might as well build TWIRL [wikipedia.org].
You're off on your orders there (Score:5, Interesting)
Check yourself there. It takes longer to perform division on larger numbers (say O(ln(N)^2), though a lot of this depends on the algorithm). If you plan to do the sieve of eratosthenes as you describe (the hard way), that's going to be another O(n*ln(ln(N)) for a total of O(n*ln(N)^2*ln(ln(n))) for each factor.
The sort of numbers you are thinking about when you say that testing via division is O(1) with hardware are 64 bit integers. The sort of semi-primes used in cryptography are on the order of 512 bits, and so (by the formula above) would take roughly 147, 184, 841, 669, 860, 395, 336, 238, 071, 097, 320, 918, 206, 612, 375, 539, 181, 907, 207, 001, 765, 334, 079, 455, 842, 963, 079, 473, 553, 687, 769, 537, 122, 026, 054, 410, 625, 268, 901, 031, 540, 756, 829, 794, 467, 840, 000 times as long.
So if your computer took a nanosecond to solve a 64 bit case (making it faster than the fastest consumer system presently available), and you had a million of them, and all 6 billion people on Earth were your friends, and each of them had a million of these uber boxes as well, and you had a way to collaborate on the problem with no overhead, it would still take you roughly 1, 920, 658, 729, 429, 876, 148, 289, 055, 386, 140, 718, 898, 913, 520, 422, 922, 263, 604, 244, 594, 006, 798, 154, 722, 944, 671, 495, 344, 450, 391, 916, 549, 249, 431, 238 times the age of the universe to factor one such number.
That's why nobody does it that way, and why it's considered a hard problem even though it might sound easy.
-- MarkusQ
Re: (Score:2)
I'll pass by the obvious "your mama" joke and just note that it's nice to see that someone with your obvious self confidence and ambition is so unpicky.
Or, I suppose, desperate.
--MarkusQ
Re: (Score:2, Informative)
Re: (Score:2)
It's ln not log.
Re: (Score:2)
The primes you want are around 300 digits long. And I'm guessing that even at ultra high numbers primes occur every google or so....
Re: (Score:2)
There are an infinite number of primes. Any elementary book on number theory will have the proof of that in it.
There's *a lot* of literature out there on how to factor integers. If you want something more readable, then look up the quadratic sieve. It's the second fastest algorithm out there. That being said, it *is* a general algorithm so its speed will likely be improved by making some modifications due to crypto using almost primes. But, that gets somewhat convoluted. Just stick to the quadratic si
Re:Kudos to Galois (Score:4, Interesting)
Clarification:
Cryptol, as I understand it, was developed by Galois [galois.com] (who, for some reason, is not mentioned in the summary) and not by the NSA. It would be interesting to know whether it was a joint decision between Galois and the NSA to release cryptol, or just Galois' decision alone.
Re: (Score:1)
Galois does high assurance computation for the NSA, and others. (Which is to say, the NSA expects Galois to do theorem proving on their code)
Does anybody have any good information about Cryptol? Is it a Haskell subset/extension? Most of what I know about Galois is in relation to Haskell.
Re: (Score:2)
There's some documentation [galois.com] on Galois' web page. I looked at it once awhile back, and it seemed a lot like Haskell, but with extra syntax for doing common cryptographic operations.
Chapter 8 of the programming guide [galois.com] has example cryptol implementations of DES, RC5, and AES.
Re: (Score:2)
That wasn't intentional. I think I must not have enclosed the "a href" tag properly. Here, let me try again [galois.com].
I assure you that there really is such a company; I have visited their offices on several occasions.
Re:Kudos to NSA (Score:5, Informative)
Just a correction: Regardless of who developed this (there seems to be some disagreement), nobody turned it over to the public domain. Read the license agreement: it says that you are not allowed to even create derivative works, nor redistribute the program to multiple sources, nor use it for commercial purposes.
Re: (Score:1)
but does this mean I cannot implement my own Cryptol interpreter or compiler?
First off, I'll just state that I'm not a laywer, this is not legal advice, and fucking with the NSA is liable to land you hot water in no time. But you probably could. My understanding is that for a programming language, the language itself would be the 'look and feel' and probably not subject to copyright or patent restrictions, but YMMV depending on your jurisdiction.
From a technical standpoint, though, it's not the language semantics itself that necessarily generates really fast binary code for cryptog
Re: (Score:2)
Far as I can see, it's a very trimmed-down formal language and not a whole lot more. Yes, a lot of the work is in the compiler, but there are plenty of well-developed compilers for languages just as well-designed, and a fair few are Open Source, not proprietary or with absurd conditions. And even those which are proprietary, such as Intel or Green Hills, the trial version is full-blown and not a toy edition. Re-implementing Cryptol as a front-end to an existing high-quality compiler, or as a translator (the
Re: (Score:2)
But Microsoft couldn't take action against Mono or any of the Open Source .Net reimplementations because that's not something that can be protected.
Yes they can, via patents.
Re: (Score:2)
Re: (Score:2)
they merely codify the syntax and semantics
It's the semantics that are patentable, at least in the United States.
Re: (Score:2)
The implementation of a business method or algorithm is patentable, but the semantics fall short of a full implementation. Also, patents are not supposed to include those things which are "obvious". You could not patent the AND operator, for example, even if there was no prior art. (Ok, the USPO gets muddled on what is "obvious", which is why the one-click patent may or may not actually be valid.) For the most part, instructions in a language are "obvious" and also have oodles of prior art. It would be very
Re: (Score:2)
Kodak wins Java patent suit [cnet.com]
"Eastman Kodak has won a controversial lawsuit in which it claimed Sun Microsystems had infringed several of its patents with its Java programming language."
Re: (Score:2)
I could be wrong, but take a look at the following extract from the linked article:
"These patents--numbers 5,206,951, 5,421,012, and 5,226,161--referred to the integration of data between object managers, and between data managers, and to the integration of different programs that were manipulating data of different types."
To me, this sounds like an implementation of Java issue, not an issue with Java as a language. You could implement all kinds of mechanisms in the JVM that did the same thing but were not
Re: (Score:2)
The point is if the specified semantics are essentially patented, you can be sued. Whether you can find an acceptable workaround ($92 million after the fact) is another matter. You may or may not be able to, depending.
This is the whole issue with .NET and Mono, which is why I took exception to your comment: "But Microsoft couldn't take action against Mono or any of the Open Source .Net reimplementations because that's not something that can be protected."
Re: (Score:1)
Except for the ones in the white house.
Re: (Score:2)
C'mon, be fair. It's a Coke Man in the white house.
Re: (Score:1)
FWIW, and for those whose interest was piqued by the parent post, (and note that I don't know anything about the GP's employment history), but I know that Volt Services is a staffing agency. They do a lot of IT contract placements to various government agencies, including NSA.
Basically, NSA employs a bunch of Ph.D's who layout all the theoretical work. They work with project managers who typically outsource all the coding.
I could tell you how I know all this, but I'd have to kill you. ;)
really? (Score:5, Funny)
So, wait, the NSA just released math?
Re:really? (Score:5, Funny)
Math 2.0
Re: (Score:2)
Unlike New Coke and New Math, Math 2.0 is really, truly the future. For reals this time.
Cryptol? (Score:4, Funny)
Sounds more like a drug than a programming language.
Re: (Score:1, Funny)
Sounds more like a drug than a programming language.
I thought it was Superman's dog's name.
Re: (Score:1)
Re: (Score:2)
Re: (Score:2)
Blue flag hanging from the left side, yeah that's the Cryptol side.
Why the precision? (Score:2, Interesting)
Is there something intrinsic to cryptographic protocols that requires a timed release?
Re: (Score:2)
Well, clearly it is. They would not have bothered otherwise...
You would like to know the moment you booted cryptoSkyNet :)
Re: (Score:2)
More to the point, wouldn't you like to know why they released it at 2:44pm instead of 2:45pm?
What do they know that we don't?
Who is lurking in the shadows outside your window?
Was that thump just a wild varmit messing around outside, or...
BOOOO!
Re: (Score:2)
Steganography?
Re: (Score:1)
That's misdirection. Internally, they use Unix time directly - but obviously for a press release they're gonna run it through strftime().
Using an NSA tool.. (Score:2, Insightful)
Doesn't it seem probable that anything created with an NSA tool will be more reversible with other NSA tools?
Re: (Score:2, Insightful)
Watch out. SELinux is made by NSA.
Re: (Score:2)
As I understand it, cryptol was developed by Galois, a private company, and not by the NSA. Whether you find this reassuring or not is up to you. However, if a tool for developing cryptographic protocols were to, say, substitute a weak algorithm in place of a strong one, in many cases it would simply fail to interoperate with any reference implementation not developed using cryptol.
Re: (Score:2)
Doesn't it seem probable that anything created with an NSA tool will be more reversible with other NSA tools?
How do you "back door" math?
Interesting for discrite math. (Score:5, Interesting)
Neat. There's some similarity to Matlab, and some to Renderman, and some of the syntax is borrowed from Haskell. The language is compilable to VHDL, so it's possible to generate hardware from the spec. The language is recursive and doesn't support iteration (there's no "for" statement) to make proof of correctness work easier.
This language might also be useful as a way to express compression algorithms. Reference implementations of the various "zip" algorithms in Cryptol would be useful, and ones for JPEG and MPEG compression, which are often implemented in hardware, even more useful. It's not clear how well Cryptol deals with memory-heavy problems like motion recognition or Hamming table building for compression, though.
Re: (Score:2)
Neat. There's some similarity to Matlab, and some to Renderman, and some of the syntax is borrowed from Haskell.
Sure, but the real fun is trying to find the cleverly concealed back door so that will allow the NSA to trivially bypass any "secure" algorithm you develop. Don't look for it in the reference implementation, as that would be too obvious and easy to work around. No, it will be somewhere in the language specification itself...
(adjusts tinfoil hat)
Wait... what? (Score:2)
Why would they release this? Don't get me wrong, I, personally, am all for donating to the community and further advancing technology as a species; however, why would the NSA deliver something to the public that would, in the long run, possibly make life harder on themselves by possibly furthering the advances of private encryption? I'm not trying to play Devil's Advocate, I just genuinely don't understand why they would (possibly) make life harder for themselves.
Re: (Score:3, Funny)
Why would they release this? Don't get me wrong, I, personally, am all for donating to the community and further advancing technology as a species; however, why would the NSA deliver something to the public that would, in the long run, possibly make life harder on themselves by possibly furthering the advances of private encryption? I'm not trying to play Devil's Advocate, I just genuinely don't understand why they would (possibly) make life harder for themselves.
Yes, why? This is as dangerous as releasing
Re: (Score:1, Funny)
... postings with fewer spelling mistakes.
Moral: Practice what you preach.
Re: (Score:2)
Re: (Score:2, Informative)
Because building hardware & software is profitable for very many companies; and getting something certified as secure enough for the NSA is pretty hard work. If they release the toolchain, it's one less thing to worry about leaking from the developer, and they have more access to better software.
Re: (Score:1)
Ok, in that capacity it makes sense. I'm not sure why that didn't occur to me earlier. Thank you, Garridan.
Re: (Score:2)
Re:Wait... what? (Score:4, Informative)
There is no such thing as trusted private encryption. Effective secure encryption is astoundingly complicated and you can not devise effective encryption in a vacuum. Lots of companies show us ineffective untrustworthy encryption which they develop in secret and which fail in short order... like CSS which is used on DVDs or the DRM in popular games and other digital media. Haven't you read folks on Slashdot mocking them for it?
So the best way is do everything out in the open and have people find the weakness in it before it goes into production. Because once it goes into production you don't need to be code breaker to enjoy the stunning stupidity of the fools that rely on private encryption... you only need to be able to find the app with google and download it.
Have a look at look at the ongoing contest for SHA-3. It's been reported here I think. Or you could the about how they came up with AES.
Here's the zoo: http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo [tugraz.at]
As a side note: Contests and prizes are remarkably effective method of spending the public's money for public good... as long as the results are open and patent free.
Re: (Score:1)
I actually didn't mean private in a "security through obscurity" sense, I meant in the private sector. It just seemed that in modern times, the United States government wouldn't want to give anything to the community in terms of improving security for individuals. (These were just the thoughts at the time, I can see why now... just thought I'd throw it out there)
Re: (Score:2)
Firstly, cryptol is being released by Galois, a private company, and not the NSA directly. I don't know the details of Galois' relationship with the NSA, but my understanding is that cryptol was developed by Galois, and it's quite likely that the NSA doesn't have any say in whether cryptol is released or not.
Secondly, there are a lot of social benefits to widespread access to good cryptography. Bad security is a constant drain on the economy, in the form of stolen credit card numbers and the like.
Thir
Finally! (Score:4, Funny)
Lack of Functionality (Score:5, Insightful)
FTFA:
"The open version does not compile to VHDL, C/C++, or Haskell, and does not produce the formal models used for equivalence checking."
So does this mean the open version (trial version) which we might have access to does not do much of what it is touted to be good for?
Just another advertisement for a commercial product methinks. Maybe cool, but still a slashvertisement.
- Toast
Re:Lack of Functionality (Score:5, Informative)
FTFA: "The open version does not compile to VHDL, C/C++, or Haskell, and does not produce the formal models used for equivalence checking."
So does this mean the open version (trial version) which we might have access to does not do much of what it is touted to be good for?
Just another advertisement for a commercial product methinks. Maybe cool, but still a slashvertisement.
- Toast
Yep. Two lines down from the above quote it states:
"Contact Galois to obtain a full-featured version for evaluation."
It's classic crippleware. Free version doesn't do anything useful, and the "full-featured" version costs money and uses a dongle or something.
Re: (Score:2)
From the download page:
So, they're providing a compiler and an interpreter. It sounds like there's enough restrictions that it would be hard to use anything cryptol-derived as part of a commercial product (or even an open-sou
Re: (Score:2)
and the "full-featured" version costs money and uses a dongle or something.
Yes, a 1048576-node supercomputer, 1 billion wire taps, and root access to the internet.
Re: (Score:2)
Now there's a problem. Galois has been dead for over 175 years.
Public Funds (Score:2)
Considering we paid for its development with public funds, it best not be 'commercially' released.
Can Cryptol programs be Free Software? (Score:3, Insightful)
Free But Shacked - The Java Trap (Score:3, Informative)
Yes, that program would be free but see "Free But Shackled - The Java Trap [gnu.org]" for more on why this situation is not desirable.
Re: (Score:2)
RMS is a nutter.
Re: (Score:2)
*sigh* :/
I wish that I had mod points for you.
Let's be civil and reasonable in disagreement. (Score:2)
How sad that you choose to engage in name-calling instead of spelling out your apparent disagreement respectfully. Before you get into that, should you choose to explain your earlier statement, you should keep in mind the remarkable history of achievement and prescience Stallman shares with us. I don't seek perfection in anyone but I can't think of too many people who have given us all so much practical useful stuff and wisdom to think about. Specifcally, it's not every hacker who writes wildly popular l
Re: (Score:2)
I don't think nutter is a particularly harsh term. Have you heard him sing?
Java is not a trap. Never was. Something like Java could have contributed to a world in which Linux on the desktop might have been more useful to more people. Java pre-installs on Windows fizzled because of legal issues, and on Linux fizzled because of unfounded fears.
Now the only de-facto universal platform is web+flash. Stallman will tell you that's a trap too.
Re: (Score:2)
Try reading the headnote of the article I linked to. The issue persists even if it will no longer apply to a dependency Sun's Java software.
Keep your kitchen clean: (Score:1, Funny)
Use Cryptol + AJAX!
Not NSA? (Score:2)
A casual perusal did not really confirm the connection between Galois.com and the NSA.
Google did not really help either:
http://www.google.com/search?hl=en&as_q=NSA&as_epq=&as_oq=&as_eq=&num=10&lr=&as_filetype=&ft=i&as_sitesearch=www.galois.com&as_qdr=all&as_rights=&as_occt=any&cr=&as_nlo=&as_nhi=&safe=on [google.com]
http://www.google.com/search?q=NSA+Galois [google.com]
Cryptol/Signali (Score:1, Interesting)
As someone that's worked with Cryptol, I can tell you that it is indeed a very cool language. You can generate very efficient hardware off of a Cryptol spec, prove logical equivalence between two versions of an algorithm, and play with your specification interactively from a command line. There's even a startup called Signali that's been founded to expand the usage of Cryptol to the commercial sector and algorithms other than cryptography.
Fedora 9: libedit.so is needed by cryptol-academic (Score:2)
$ root yum install libedit
Loaded plugins: refresh-packagekit
Setting up Install Process
Parsing package install arguments
Package libedit-2.11-1.20080712cvs.fc9.i386 already installed and latest version
Nothing to do
$ root rpm -i cryptol-academic-1.8.1-0.i386.rpm
error: Failed dependencies:
libedit.so is needed by cryptol-academic-1.8.1-0.i386
$ cat /etc/issue
Fedora release 9 (Sulphur)
Kernel \r on an \m (\l)
Next...
Why? Doesn't this seem odd? (Score:2)
IANAC (I am not a cryptographer.) but wouldn't this be a useful tool for criminals and terrorists? It would seem the height of folly to give such a tool away to them ... unless there was a way of mitigating it's usefulness.
There is no free lunch.
Not public domain, available against conditions (Score:2)
Ok, there still seems to be confusion on it being "publicly" available. This is payware with a limited trial version. The headline is about that this advanced suite (I presume, I haven't used it myself) has become available *at all*. Previously, I presume, you could not just buy it. Of course, I also presume you could freely download it from some hacking site, but that's beside the point. Law only counts for law abiding citicens.
Re: (Score:1)
Bruce Perens posts as an AC?!?!