Slashdot Mirror

← Back to Stories (view on slashdot.org)

Cryptol, Language of Cryptography, Now Available To the Public

Posted by ryuzaki0 on from the new-toys-to-play-with dept.

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.

32 of 140 comments (clear)

  1. Crack this! by mugnyte · · Score: 2, Funny

      41R5T 3N6RI27ED P057 !

    1. Re:Crack this! by Tubal-Cain · · Score: 2, Funny

      41R5T 3N6RI27ED P057 ! >>>> I AM 16 LOL!!1!1one1

  2. Kudos to NSA by rindeee · · Score: 5, Interesting

    Having worked at the Agency I must say that the quality of the 'product' that they turn over to the public domain is second to none (well, except for that which they keep for themselves of course). They take a lot of heat at a leadership level, some warranted, some not. In the end, the caliber of the engineers, security professionals and JPG (just plain geeks) that work there is second to none. From SEL to crypto bake-offs to the submitter's topic, they've done a helluva lot of good for the community. Thanks guys! Now if they could just get 'Weed Man' to open an omelet shop out in town, all would be right with the world (inside joke, sorry).

    1. Re:Kudos to NSA by caramelcarrot · · Score: 5, Funny

      That "M+" button on your calculator that no-one knows how to use. That's what it does.

    2. Re:Kudos to NSA by collinstocks · · 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.

    3. Re:Kudos to NSA by v1 · · 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 anything it divides by, it's a new prime (add it to your list) or its smallest factor is larger than your biggest known prime. Otherwise remember that factor, and start working on the dividend.

      Why is this always considered such a hard thing to do? It looks like something that should go quick.

      Heck with modern day processors I'd imagine you could fab a specialized chip that determines which of the "known primes" the provided number has as one of its divisors as a one-step (parallel) operation. Just hardcode it to those primes.

      --
      I work for the Department of Redundancy Department.
    4. Re:Kudos to NSA by Anonymous Coward · · Score: 2, Funny

      I use that to store "5318008" in memory so I always have one on hand.

    5. Re:Kudos to NSA by Chyeld · · Score: 4, Informative

      There are infinitely many prime numbers.

      The oldest known proof for the statement that there are infinitely many prime numbers is given by the Greek mathematician Euclid in his Elements (Book IX, Proposition 20). Euclid states the result as "there are more than any given [finite] number of primes", and his proof is essentially the following:

      Consider any finite set of primes. Multiply all of them together and add 1 (see Euclid number). The resulting number is not divisible by any of the primes in the finite set we considered, because dividing by any of these would give a remainder of 1. Because all non-prime numbers can be decomposed into a product of underlying primes, then either this resultant number is prime itself, 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. Either way, there is at least one more prime that was not in the finite set we started with. This argument applies no matter what finite set we began with. So there are more primes than any given finite number.

    6. Re:Kudos to NSA by cromar · · Score: 3, Interesting
      Interesting question. You always hear that it's because of "prime factorization" or something, and to tell the truth I hadn't thought about what that actually meant. The article on RSA at Wikipedia seems informative:

      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."

    7. Re:Kudos to NSA by pointsofdata · · Score: 2, Informative

      While I am no expert in the area, nor do I know a huge amount about mathematics, wikipedia says that there are:2,220,819,602,560,918,840 primes below 10^20, which is 20 digits long. Considering that the largest known prime is almost 13 million digits long,and most of these numbers are unimaginably vast, it appears that it is not trivial to find the prime factors of a number. For instance, If a computer can test 10 billion primes a second (which is more than a consumer grade computer can (I think)), then it would take ~2 billion seconds to go test all the primes from 2 to the 10^20. While this would be far faster on a supercomputer, if all primes up to 2^(43,112,609) â' 1 are taken into account, it is not hard to appreciate that this will take a huge amount of time.

    8. Re:Kudos to NSA by 644bd346996 · · Score: 2, 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.

    9. Re:Kudos to NSA by akaariai · · Score: 2, Informative

      The short answer is that there is just too many primes to list. There is about x/log(x) prime numbers smaller than x. If you have a 512 bit number then you have about sqrt(2^512) / log(sqrt(2^512)) numbers to check. So, there is 1.5 * 10^75 numbers you need to list. This is simply impossible. Moore's law will not help here, as adding one bit to the number to check about doubles the search space. That is, after a year of you can check a number that is just one bit larger!

    10. Re:Kudos to NSA by Chyeld · · Score: 2, 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 three, you can't divide into the result cleanly.

      This is going to be the same for any group of prime numbers you pick. By adding 1 to their product, the result can't be broken down cleanly as a product of those numbers. You'll always be 1 away (because you actually took their product and added 1).

      Now the definition of a prime number is a number that can only be cleanly divided by two numbers. Itself and 1. Every other number has more possible divisors. As a result of this, every number out there is either a prime, because you can't divide something into it, or a product of primes.

      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.

      That means, by default, our group of numbers can't contain all the prime numbers. Either they are missing our result (and btw, 31 is a prime) or they are missing the prime factors of our result. And since this works for any group of prime numbers you can put together, effectively you've just proven that the actual set of prime numbers itself is infinite.

    11. Re:Kudos to NSA by Anonymous Coward · · Score: 2, Funny

      Is there anything that little button can't do? I have a feeling "M+" stands for "More magic".

    12. Re:Kudos to NSA by MichaelSmith · · Score: 3, Funny

      There are infinitely many prime numbers.

      The GP said the number of primes is essentially fixed which is consistent with the number of primes being infinite, I suppose.

      --
      http://michaelsmith.id.au
  3. really? by gclef · · Score: 5, Funny

    So, wait, the NSA just released math?

    1. Re:really? by BitZtream · · Score: 5, Funny

      Math 2.0

      --
      Persistent Volume manager for Kubernetes - https://github.com/dwimsey/openshift-pvmanager
  4. Cryptol? by larry+bagina · · Score: 4, Funny

    Sounds more like a drug than a programming language.

    --
    Do you even lift?

    These aren't the 'roids you're looking for.

  5. Why the precision? by Anonymous Coward · · Score: 2, Interesting

    Available To the Public on Friday December 26, @02:44PM

    Is there something intrinsic to cryptographic protocols that requires a timed release?

  6. Re:Using an NSA tool.. by Anonymous Coward · · Score: 2, Insightful

    Watch out. SELinux is made by NSA.

  7. Interesting for discrite math. by Animats · · 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.

  8. Wait... what? by Vertana · · 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.

    --
    "The best way to accelerate a Macintosh is at 9.8m/sec^2" -Marcus Dolengo
    1. Re:Wait... what? by Bazzargh · · Score: 2, 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 a dictionary - possibly allowing wildly speculative internet postings with less spelling mistakes.

      Down with that sort of thing! Careful Now.

      - Father ted.

    2. Re:Wait... what? by Garridan · · 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.

    3. Re:Wait... what? by bhima · · Score: 3, 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

      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.

      --
      Nothing in the world is more dangerous than sincere ignorance and conscientious stupidity.
  9. Finally! by tobiasly · · Score: 3, Funny

    At last, we now have a programming language that implements rot13() natively! Now my website's login authentication system will really fly...

  10. Lack of Functionality by burning-toast · · 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

    1. Re:Lack of Functionality by Dun+Malg · · Score: 4, 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.

      --
      If a job's not worth doing, it's not worth doing right.
  11. Re:Kudos to Galois by j1m+5n0w · · Score: 3, Interesting

    Clarification:

    Cryptol, as I understand it, was developed by Galois (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.

  12. Can Cryptol programs be Free Software? by Krishnoid · · Score: 2, Insightful

    So if someone used Galois to release a binary, and released the Cryptol source under the GPL, would the resulting binary be considered Free Software per the FSF's definition?

  13. You're off on your orders there by MarkusQ · · Score: 4, Interesting

    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 anything it divides by, it's a new prime (add it to your list) or its smallest factor is larger than your biggest known prime. Otherwise remember that factor, and start working on the dividend.

    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

  14. Free But Shacked - The Java Trap by jbn-o · · Score: 2, Informative

    Yes, that program would be free but see "Free But Shackled - The Java Trap" for more on why this situation is not desirable.

    --
    Digital Citizen