Schneier on Security

maqp • September 6, 2019 6:19 PM

@Tatütata

Another aspect to the timeline:

At 4:14 of https://www.youtube.com/watch?v=MLb95ESwy60 the interviewer asks Grant what the implication of finding quasi primes is, to which Grant responds he does not know enough to know how profound the implication is. According to the video (3:53) it was filmed on March 19 (day before the paper was published arXiv). The Time AI marketing crap was uploaded on March 28.

So in just ten days Grant was able to figure out it meant he could break RSA, come up with the implementation, discover a quantum encryption algorithm to replace RSA, design and render the video, and push it for to the world to see.

In comparison, it took the Hold My Ark six days longer to cut and publish Grant’s interview.

maqp • September 14, 2019 2:10 PM

I’ve been looking into the Crown Sterling stuff a bit and one of the more interesting parts IMO is Grant’s Instagram account: https://www.instagram.com/robertedwardgrant/

From what I’ve gathered, there seems to be three things Crown Sterling is currently working on

1. The 24-sided dart board with spooky remainders of primes mod 24 — that when finding new primes, allows reducing the search space by two thirds (the effect is so insignificant, such speedups are ignored in the Big O notation). The most interesting part here is IMO that apparently the Knight’s Templar have predicted primes with the help of tomatoes.
2. Breaking of the RSA.
3. Developing their Time AI public key encryption algorithm.

The section 1 has been hashed over and over, and section 3 has nothing published on it yet (I doubt there ever will be). But 3 isn’t important until they show they can break RSA (section 2) so it’s this one I want to draw attention to.

For some reason Grant is more open about his research on Instagram (might be because it doesn’t intersect with the infosec bubble calling out his bullshit, and because his fanbase likes to look at his wanna-be da Vinci doodles).

One specific post I want to highlight is this one:

New Mathematical Discovery: The exact factors (5987 x 6323) of this Bi-prime 37,855,801 appear contiguously and perfectly within its 1/x reciprocal value (1/37,855,801) string. Since realizing the above, our research team has tested many Biprimes to see whether their factors appear in their respective 1/x reciprocal values and also how they may relate to the “period” (repetition) of those values (in repeating rationals).

For non-Unique (have period lengths that no other prime possesses) and non “Period” Primes where their period is substantially less than the scale of the number) it appears that their two prime factors, regardless of length appear inside their reciprocal decimal extensions! As the period for these numbers is generally quite large, one must extend the length of these decimal extensions at least long enough to surpass their first Period cycle.

Paradoxically, the longer the BiPrime you desire to factor, the easier to locate the long consecutive prime string embedded within its 1/x reciprocal value. I believe that this realization will have major ramifications in many fields of science and cryptography. It also says that numbers could never have been invented by Mankind, the degree of sophistication and analysis necessary to accomplish this is so far beyond even the world’s current understanding and comprehension of the language we call Mathematics.

This is fascinating work as we believe it says something very fundamental about the “Source Code” of numbers in general, and implies a deeper numerical meaning within nature’s elegant complexity, yet beautiful simplicity. These decimal extensions also appear to possess Wave characteristics (similar to constants) both in their period values as well as the distance between factors and how this also relates to periodicity. Perhaps the 1/x value is a veritable DNA ???? for numbers themselves. It’s a brave new world. Feels like we are on the verge of something really big that will unpack the nature of DNA and our awareness (and purpose) of numbers generally.

There’s two aspects to this

1. It doesn’t hold true for all primes. I wrote a tiny program that shows this: https://pastebin.com/uua5Jnxx Grant and his team acknowledge this in one of the Instagram posts but it doesn’t stop them from fear mongering.

2. The efficiency of the algorithm (“search for prime factors in the recurring decimal of the reciprocal of the semi-prime”) is ridiculously slow and requires ridiculous TMTO.

You first need to find the period of the semi-prime. It might be trivially doable with 2-6 digit semi-primes, but even the trivial RSA-100, broken in 1991, has 100 digits:

n = 15226050279225333605356183781326374297180681149613
80688657908494580122963258952897654000350692006139

a) Assuming n is not relatively prime to 10, determining the period with brute force takes too long. I’d appreciate if someone did the math.

b) Even if the period could be determined, to avoid having to calculate the decimal expansion again every time, it needs to be stored on memory. The period length is at worst n-1 so writing down the entire period takes at worst n-1 bytes, or 10^83 petabytes (there are only 10^82 atoms in the observable universe).

c) My conjecture is, it is actually quite likely the prime factors (37975227936943673922808872755445627854565536638199, 40094690950920881030683735292761468389214899724061) would be found on memory where every atom of our universe has been manipulated to contain petabytes of decimals.

The problem is, even with the TMTO, you still need to check practically every offset of that memory to see if what you tested is indeed a factor of the semi-prime. This takes in the order of n operations, and is thus completely infeasible.

In his post Grant says “I believe that this realization will have major ramifications in many fields of science and cryptography.” The ramifications can be evaluated by considering Grant’s “discovery” takes forever to run even with smallest numbers, and by considering the GNFS algorithm can factor RSA-100 in seconds on modern HW.

So, if RSA-100 is too slow, what chance does Crown Sterling have against the RSA-2048 challenge, where the semi-prime is

RSA-2048 = 2519590847565789349402718324004839857142928212620403202777713783604366202070
7595556264018525880784406918290641249515082189298559149176184502808489120072
8449926873928072877767359714183472702618963750149718246911650776133798590957
0009733045974880842840179742910064245869181719511874612151517265463228221686
9987549182422433637259085141865462043576798423387184774447920739934236584823
8242811981638150106748104516603773060562016196762561338441436038339044149526
3443219011465754445417842402092461651572335077870774981712577246796292638635
6373289912154831438167899885040445364023527381951378636564391212010397122822
120720357

Now, Crown Sterling would obviously say that this isn’t how they broke RSA which begs the question — if they already have factoring algorithm that runs in polynomial time, why waste time on “new discoveries” such as this, that don’t offer any speedup at all?

But surely there’s something else going on because as per this post’s reasoning it’s obvious they couldn’t use this method to win the challenge they threw at JP Aumasson about factoring a 512-bit semi-prime. (Apparently they were thin-skinned enough to convince some random youtuber, which I find hilarious). So assuming the comment wasn’t staged, how did they do it?

My guess is they did what Theranos did and tried to convince people they have something by running existing technology: e.g. GNFS on AWS.

But what about the discovery? I think it’s possible that if they did what Theranos did, this was created to please the investors: another spooky phenomenon that is easy to follow, appears to offer big results, and that requires a course on algorithm design to determine it’s useless on big numbers.

More and more I think the fraud here seems to be misleading the audience and especially the investors by showing patterns that leads to them drawing bad conclusions.

E.g. one of the questions the Instagram post has, is

Does this mean the end of public-key encryption based on prime factorization?

to which Grant replies

I have already stated publicly that all factor based encryptions are now, in my opinion, highly vulnerable. and this statement stands independent of size of the public key.

He doesn’t claims this discovery will break RSA, but implies that by presenting the two next to each other. There’s room for deniability too: he could later say “I was only answering a question and it had nothing to do with curious properties of decimal expansions the image was about!”.

Another example is his youtube interview where he says

When I realized my discovery might have a significant impact on the way encryption is done–

He is not saying his discovery has an impact on the security of RSA, but “how encryption is done”, i.e. what he can make people use, i.e. what he can sell to you. It’s just the listener’s mind that makes these conclusions from the context.

maqp • September 17, 2020 12:42 PM

@Clive Robinson

“In essence the Internet has enabled such people to “find each other” thus reinforce their cherrished lack of ability so the problem is only going to get worse before it gets better…”

I agree. My conjecture is the problem with disinformation, cults, echo chambers, and bullshit is going to get incredibly bad, and this will at some point be over-compensated with a social movement that will re-emphasize significance of reputation to the point of zero tolerance. It’ll probably feature cancel culture where it’s enough to be caught of lying, and over time, even caught of inaccuracies.

Or alternatively the political polarization will continue until it’ll lead to outright civil war, after which — to quote Churchill — it doesn’t matter who was right, the truth is determined by who is left.

The first option I think is less likely and less dangerous, but I don’t see either correcting movement is going to improve situation in itself, it’s only after the aftershocks that we see calm.

maqp • December 3, 2020 9:11 AM

The scam continues. There’s a Token Offering so sounds like they’re pivoting their scam to crypto currencies.

https://vimeo.com/486166742

The registration part (https://www.crownsterling.io/portal-registration/) contains the following NDA

Crown Sterling Limited, LLC, a Delaware limited liability company (which together with its subsidiaries and affiliates relevant to its business is hereinafter referred to as the “Company”) and its agents are prepared to make available to you certain information relating to the Company (the “Information”) regarding access to encryption services to be provided by the Company. Certain of the Information is confidential and non‑public, and proprietary to the Company.

In consideration of providing this Information to you, you acknowledge and agree that in connection with your receipt of the Information, you and your advisors will hold and maintain the Information (other than Information that is available to you on a non‑confidential basis) in confidence and not use the Information except in connection with evaluating the encryption services for your own use or disclose it to any other person, except to the extent required by applicable laws or process (and you will cooperate with the Company in contesting any such process). At any time on request you will (and will cause your advisors to) return to the Company all Information and destroy all writings (including digital representations thereof) relating thereto or based thereon prepared by you or any of them.

This letter agreement shall be governed by the laws of the State of California, USA. You and we irrevocably agree that for any dispute in relation to this letter that cannot be amicably settled between yourself and ourselves, to refer to arbitration to take place in Orange County, California under the Rules of Comprehensive Arbitration before the Judicial Arbitration and Mediation Service (“JAMS”), appointing one arbitrator and the language to be used is English. We shall be entitled to seek either or both monetary damages and equitable remedies. The prevailing party shall be entitled to recover reasonable attorney’s fees and costs.

So you’re only allowed to evaluate the security for yourself, and you’re legally bound not to tell anyone about your findings. This is the literal opposite of the industry best practice, i.e. peer-reviewable, open, transparent tech. What the NDA says is

“If you’re smart enough to tell we’re bullshitting you with our “tech”, you can’t tell others we’re scamming them or we’ll sue you”. I’m not surprised at all about this.

maqp • December 3, 2020 12:43 PM

@Clive Robinson

“Probably they think long enough that it’s no longer in common memory…”

Indeed. I’m not sure if they realize they’ve become infamous withing infosec circles, it’s a stain that will never come off. The sad thing is the gullible investors aren’t necessarily part of that group.

Hard to say which of their crap sells (the healing crystals just might), but I’d imagine the crypto currency scam will work given that Bitcoin price keeps climbing, and they’ll miss a new opportunity to make a fortune.

maqp • December 26, 2020 9:09 PM

I had a chat with a buddy of mine (Topi Talvitie) who’s a postdoc researcher here at Helsinki Uni. He reverse engineered the logic on how a fake solver algorithm, such as the one “Pythagorean Factoring” by Grant’s, can be created trivially. The post is quite long so I put it on gist:

https://gist.github.com/maqp/ced7e90f70131f95f6465a7f782acf1b

The post first translates how Topi reasoned it (the translation needs some work), I then slightly expanded his work by focusing on describing how to hide the private values inside the pre-baked triangle. I also included some real numbers in the hope that it helps readers less seasoned in math to keep track of what’s happening.

maqp • December 26, 2020 10:20 PM

@xcv

“You’re searching for Pythagorean triples”

The value for B in the example is sqrt(public_key), it’s not a requirement that all three sides are integers.

The reduced version of Grant’s solver could also be expressed the form of

import math
public_key = …
B = math.sqrt(public_key)
for A in range(0, 2**1024)):
C = math.sqrt(A**2 + B**2)
p = C-A

if public_key % p == 0:
q = public_key / p
print(f”{p}, {q}”)
exit(0)

It doesn’t matter whether the algorithm checks if p is a valid factor of public_key by multiplying it with q and comparing against public_key, or if it checks that public_key % p == 0. What matters here is the complexity class which is exponential and that it’s just another brute force attack.

Whether or not integer factorization problem is a Diophantine equation, isn’t really of importance.

maqp • December 26, 2020 10:24 PM

@Moderator the pre-format feature on the page appears to be broken.

@xcv one more time: https://pastebin.com/raw/bVqXaq02

maqp • December 29, 2020 3:12 PM

I finally saw Grant’s video and realized his Excel spreadsheet wasn’t actually a lookup table, but a crap O(n^2) implementation of Fermat’s factorization method.

@xcv: Here’s the time-complexity graph on small key sizes. When adjusted, it’s obvious the time complexity of the algorithm is exponential: https://i.imgur.com/wC1JT8A.png

I rewrote most the Gist post as my conjecture about what Grant was iterating over, was off: It was about “x”, not about “A”.

https://gist.github.com/maqp/0f5351a71d33a2ebc6799b8b54764b41

The interesting new aspect here is the Fermat’s method, as that allows them to effectively cheat in their demo: by cherry picking semiprimes the prime factors of which are relatively close to one another, that allows them to stumble on correct factors extremely quickly when demoing the “cracking algorithm”, even though the expected number of iterations for x is usually around sqrt(rsa_moduli). Manufacturing such cherries is also absolutely trivial.

What Grant et. al. fail to mention is e.g. NIST has clear definitions about the minimum distance of the prime factors: https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-56Br2.pdf (page 47), and that implementations such as OpenSSL explicitly check that the limits set in the NIST spec are fulfilled.

maqp • October 5, 2021 1:56 AM

It seems editing the submission before posting breaks URLs for some reason, so let’s try again:

Whitepaper: https://www.crownsterling.io/wp-content/uploads/2021/09/Crown-Sterling-Lite-Paper-.pdf

Twitter thread: https://twitter.com/markus_ottela/status/1445268250003181568