Submitted via IRC for Bytram
Medicine show: Crown Sterling demos 256-bit RSA key-cracking at private event
On September 19, in a conference room at the Pelican Hill Resort in Newport Beach, California, Crown Sterling CEO Robert Grant, COO Joseph Hopkins, and a pair of programmers staged a demonstration of Grant's claimed cryptography-cracking algorithm. Before an audience that a Crown Sterling spokesperson described as "approximately 100 academics and business professionals," Grant and Hopkins had their minions generate two pairs of 256-bit RSA encryption keys and then derive the prime numbers used to generate them from the public key in about 50 seconds.
In a phone interview with Ars Technica today, Grant said the video was filmed during a "business session" at the event. The "academic" presentation, which went into math behind his claims and a new paper yet to be published, was attended by "mostly people from local colleges," Hopkins said. Grant said that he didn't know who attended both sessions, and the CEO added that he didn't have access to the invitation list.
During the presentation, Grant called out to Chris Novak, the global director of Verizon Enterprise Solutions' Threat Research Advisory Center, naming him as a member of Crown Sterling's advisory board. The shout-out was during introductory remarks that Grant made about a survey of chief information security officers that the company had conducted. The survey found only 3% had an understanding of the fundamental math behind encryption.
The video of the demonstration is here. (The video was briefly marked as private, but is now back again.) The demo was displayed from a MacBook Pro, but it appeared that it was being run in part via a secure shell session to a server. Grant claimed that the work could be used to "decrypt" a 512-bit RSA key in "as little as five hours" using what Grant described as "standard computing."
The demonstration only raises more skepticism about Grant's work and about Crown Sterling's main thrust—an encryption product called Time AI that Grant claims will use the time signature of AI-generated music to generate "quantum-entangled" keys. Grant's efforts to show how weak long-cracked versions of RSA are was met with what can only be described as derision by a number of cryptography and security experts.
Mark Carney, a PhD candidate at the University of Leeds, used Msieve, a well-established factoring method, on his laptop. Carney cracked compound numbers larger than RSA keys into primes in about 20 seconds. "These [were] not 256-bit keys, just larger-than 256-bit numbers," he explained, but "these are using standard quadratic sieve methods. So long as I haven't messed this preliminary test up too much, this is un-optimized Msieve out-performing Crown Sterling's algorithm by roughly 50 percent."
Henryk Plötz, a computer scientist in Berlin, ran a test of his own, with similar results:
Well, this is Sagemath on my Ultrabook (X1 Carbon 2017).
I'm assuming the default implementation is single-threaded. So, "50 seconds" is exactly the expected performance on a 4-core laptop. pic.twitter.com/2WlvZaR0vk— Henryk Plötz (@henrykploetz) September 20, 2019
Related: Claim: SHA-256 has been Broken
Related Stories
Arthur T Knackerbracket has found the following story:
The Wall Street fintech Treadwell Stanton DuPont broke silence today as it announced its Research & Development and Science Teams successfully broke the SHA-256[*] hashing algorithm silently in controlled laboratory conditions over a year ago. The announcement aims to secure financial and technological platform superiority to its clients and investors worldwide.
[...] While the best public cryptanalysis has tried to break the hashing function since its inception in 2001, work on searching, developing and testing practical collision and pre-image vulnerabilities on the SHA-256 hashing algorithm began back in 2016 in Treadwell Stanton DuPont's R&D facilities, culminating 2 years later with the successful discovery of a structural weakness and the initial development of the first practical solution space of real world value by its researchers.
"While we have successfully broken all 64 rounds of pre-image resistance," said Seiijiro Takamoto, Treadwell Stanton DuPont's director of newly formed Hardware Engineering Division, "it is not our intention to bring down Bitcoin, break SSL/TLS security or crack any financial sector security whatsoever."
[*] See the SHA-2 page on Wikipedia for background on SHA-224, SHA-256, SHA-384, SHA-512, SHA-512/224, and SHA-512/256.
A blogger with the handle "Soatok" has written about considerations in safely using RSA. His first recommendation is not to use RSA at all any more. Failing that, if you must use RSA, he has various recommendations to mitigate the problems that using RSA entails.
Every RSA keypair must be represented as all of the following:
- RSA Secret Key (sk)
- Operation (sign or decrypt)
- Mode (padding or KEM-DEM)
- Hash function (signatures, MGF1)
- Modulus size
- Public exponent
- RSA Public Key (pk)
- Operation (encrypt or verify)
- Mode (padding, etc.)
- Hash function (signatures, MGF1)
- Modulus size
- Public exponent
Any time you change any of these configuration parameters, it MUST be used with a new asymmetric key-pair. The new key MUST NOT be used with the same raw key bytes as any previous key.
Elliptic Curve Cryptography (ECC) is apparently easier to work with, but both will be susceptible to cracking with quantum computers some day.
Previously:
(2019) Crown Sterling Demos 256-bit RSA Key-cracking at Private Event
(2016) Upgrade Your SSH Keys
(2015) 512-bit RSA Keys Cracked in Four Hours for only $75
(2014) NSA and RSA - Claims of More Evidence
(Score: 2, Informative) by Anonymous Coward on Sunday September 22 2019, @11:15AM (1 child)
"Crown Sterling Claims to Factor RSA Keylengths First Factored Twenty Years Ago"
https://www.schneier.com/blog/archives/2019/09/crown_sterling_.html [schneier.com]
(Score: 3, Touché) by janrinok on Sunday September 22 2019, @12:40PM
Did you look at the 'Related' in the main story? That was based on the original story [soylentnews.org] we published on 11/09/19, which was itself based on reporting from various sources including Scheier.
An a few days ago Schneier added the following:
If you read the dept you will see that we have suggested that the claim is looking less likely to be true as a result of the source for this story and that the demonstration of the claim was far from convincing.
I am not interested in knowing who people are or where they live. My interest starts and stops at our servers.
(Score: 2) by JoeMerchant on Sunday September 22 2019, @11:55AM (13 children)
256 in 50 seconds
257 in ~100 seconds?
258 in ~200 seconds...
...
512 in ~1.8*10^71 years?
Even if it doesn't scale linearly with the search space, it scales.
Moore's law has scaled up computing power by a factor of 100,000 in the last 30 years or so. Quantum methods might put a dent in the scaling factor (BTW, completely trashing the Bitcoin classic blockchain, unless you start adding a regular audit and global acceptance interval to it...) but... extend those keys a bit and they'll stay secure for many years.
And, if you are so interested in me that you're trying to read my "private" mail when I'm dead - thanks, appreciate the attention, most of the other 8 billion dead slobs out there don't rate that level of attention.
🌻🌻 [google.com]
(Score: 0) by Anonymous Coward on Sunday September 22 2019, @12:39PM (1 child)
MOORE'S LAW IS THE CONSTRUCT OF A HUMAN MIND. SORRY ABOUT THE CAPS.
(Score: 2, Funny) by Anonymous Coward on Sunday September 22 2019, @10:49PM
You're sorry about... the caps? WHAT ABOUT THE BULLSHIT?
(Score: 2) by pipedwho on Sunday September 22 2019, @07:26PM (6 children)
Since the density of primes is not the same as the density of the ordinals, the growth isn’t quite equal to a power of two.
It is generally accepted (and noted by RSA itself) that for an equivalent security AES128 it would require at least RSA 3072. And for comparison RSA2048 is equivalent to 112 bits and RSA1024 is equivalent to 80bits.
Going by these numbers RSA256 is utterly trivial. And showing that you have a program can crack it is equivalent to showing that you can crack AES32 or some other trivial reduction.
There’s a tool called Yafu that already does this and the wiki page mentions a factorisation of RSA256 in 100 seconds and RSA192 in 4 seconds. I’m sure that page is from a few a back. Today I’d expect it to be quicker.
Basically: nothing to see here, move along.
(Score: 2) by JoeMerchant on Sunday September 22 2019, @07:41PM (5 children)
🌻🌻 [google.com]
(Score: 2) by pipedwho on Sunday September 22 2019, @10:58PM (4 children)
But extending an RSA by doubling it’s size give you about 32 bits of additional effective AES equivalent security.
Adding an extra few bits to an RSA key isn’t going to do much. To get an equivalent of 256 bit AES you need a 15000+ bit RSA key.
So you’re right that extending key sizes improves security, but showing that a 256bit RSA key can be broken says nothing. People might do some basic (invalid) math and assume that a 512 bit RSA might take 2^256 times the 50 seconds. Obviously (to us) this is not the case due to the nonlinear reductions as size grows with algorithms used for factorising. Whereas doubling the size of a 128 bit AES key grows the effort by the full 2^128 increment.
(Score: 2) by JoeMerchant on Monday September 23 2019, @01:31AM (3 children)
No might about it, that will happen, frequently.
Back in 1989, I sat through a rather boring semester of graduate level cryptography. I expect they have the same courses today. I would hope that any company getting their hands dirty with roll their own keylength and other algorithmic choices would have at least one team member who has the equivalent of that course, or self-study at that level. Hope in vain, I am certain, because nobody on the business side of most ventures really know or care how it works, to them it's all encrypted all the time - no fancy algorithms required.
🌻🌻 [google.com]
(Score: 2) by opinionated_science on Monday September 23 2019, @11:15AM (1 child)
I read about RSA in Knuth, Vol 2.
I suppose I may need to update my knowledge, but for RSA, that was a pretty good treatment.
(Score: 2) by JoeMerchant on Monday September 23 2019, @02:47PM
Now, three decades later, the only thing that I truly took away from that course is: asymmetric encryption using public/private key pairs is a thing. Which, I suppose, is not a total waste of three credit hours.
If I were to do anything that really "mattered" with encryption, I'd self-study the source material until a clear picture came through - not a "oh, I can barely see how to make this look like it's working" level of understanding, which - to be honest - is better than average in most of the field, but an actual: "here are the available parameters and this is what happens as you adjust them..."
Since I mostly just dabble with crypto-tech as thought exercise / hobby, my favorite implementation is: algorithm X - insert whatever is appropriate, and make sure your coding / data designs can handle changing X to Y to Z without a major rewrite. This, too, seems beyond many of the "serious" implementations out there...
🌻🌻 [google.com]
(Score: 2) by pipedwho on Tuesday September 24 2019, @12:37AM
Sad, but true.
(Score: 2) by FatPhil on Monday September 23 2019, @11:09PM (3 children)
Things don't scale quite that way.
Trial division (stupid) would scale with p, not n, so would grow 128 powers of 2 not 256.
The decreased density of primes would make that 127, not 128.
However, TD's not how you find factors, even if you're lazy, as there are p^(1/2) methods, so that would be 64 powers of 2.
Those methods are also obsolete, but the better methods don't have easy expressions for their growth. But we're talking under 10 powers of 2.
HOwever, for challenges like these (equal sized numbers) you don't use factor-finding algorithms (probability of finding a factor correlates negatively with the size of the factor), you use composite-splitting algorithms (factor size is irrelevant). These also have remarkably similar growth expressions, in particular in that kind of range.
These better methods are easily available for all platforms, so there's no need to write your own, just use what the professionals (academics pushing the field forward) use. So they, as can anyone in the world, factor RSA-512 in a few hours on a single grunty box.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by JoeMerchant on Tuesday September 24 2019, @01:19AM (2 children)
Clever minds at work draw down 256 bits of additional RSA key to roughly 1000x the search space, or 512 to a million, 1024 to a trillion, etc. which probably explains the most recent recommendation I read for 3072 bits as "good enough for now" - but, I noticed no objectionable delays in generating and using 4096 bit keys, so, what the hell, go for the extra factor of a trillion in the brute force breakage time - makes the $5 wrench approach that much more attractive.
🌻🌻 [google.com]
(Score: 2) by FatPhil on Tuesday September 24 2019, @07:57AM (1 child)
UIUC prof DJB wrote a paper about how dedicated h/w could radically improve factoring time and more importantly lessen factoring time growth, but the crypto world poohpoohed that as scaremongering (and because some of them had designed the crypto scheme in the first place, or were hangers on, and took DJB's delivery as insulting - it got dirty). So far, no progress has been made implementing such a scheme, so maybe RSA were right after all, and DJB was wrong, but DJB doesn't have a reputation for being wrong.
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves
(Score: 2) by JoeMerchant on Tuesday September 24 2019, @12:30PM
Clever people will eventually break most things, whether that's by parallel cracking across millions of CPUs or quantum processing or whatever. And, there are alternatives to RSA, but I haven't seen a need to abandon RSA just yet - I suspect if an academic cracks it, we'll be hearing about it shortly before the paper even goes for consideration for publication. If a government cracks it, we'll see something like the Langley compute farm adding an additional nuclear power plant to feed the cracking machines.
🌻🌻 [google.com]
(Score: 1) by drgibbon on Sunday September 22 2019, @12:47PM
Please fix the headline.
Certified Soylent Fresh!
(Score: 5, Interesting) by stormwyrm on Sunday September 22 2019, @02:14PM (2 children)
There are several RSA challenge numbers that no one has yet factored. The highest one that has been factored so far was RSA-230. Let's see them factor:
133294399882575758380143779458803658621711224322668460285458826191727627667054255404674269333491950155273493343140718228407463573528003686665212740575911870128339157499072351179666739658503429931021985160714113146720277365006623692721807916355914275519065334791400296725853788916042959771420436564784273910949
That's RSA-1024, and it would be convincing even if it takes them a year to do so. That would be a suitable demonstration, since the only way that anyone will be able to factor that kind of number armed only with today's technology and publicly known mathematical knowledge is if you had a bespoke supercomputer with terabytes of very fast memory. The general number field sieve (GNFS), the fastest known factoring algorithm in the open literature, would be much too slow if you were to rely only on today's ordinary commercial off the shelf computer hardware. The memory bandwidth and latency of even the fastest standard buses available now is much too slow for the GNFS to factor a 1024-bit number. It's probably feasible under the budget of an intelligence agency that has the perhaps billions of dollars to pay Cray or some other supercomputer manufacturer make the hardware to spec. So anyone who can produce the prime factors of RSA-1024 on or before September 22, 2020 is probably onto something big. Either that, or they've hacked the NSA's own supercomputers. :P
Numquam ponenda est pluralitas sine necessitate.
(Score: 2) by edIII on Monday September 23 2019, @01:50AM
I bet I could do that. *I* solved one of those triangle puzzles at Cracker Barrel.
Technically, lunchtime is at any moment. It's just a wave function.
(Score: 2) by FatPhil on Monday September 23 2019, @11:14AM
And of course, these are *toy numbers*, as you say. They claim they can do RSA-512 in 5 hours in the youtube vid, which again is about a few dollar's work on Amazon rental node. However, they are puffing themselves up to sound actualkly interesting to the factoring community - their tech "will let us crack 1024 and 2048 very very rapidly".
Don't watch the youtube vid - you'll be grinding your teeth at their horrible mangling of terminology, they clearly don't know what they're talking about. Did you know that the "discrete logarithm", which is what they use to split the composite into its factors, is a "one way street" function?!
Great minds discuss ideas; average minds discuss events; small minds discuss people; the smallest discuss themselves