An Almost-Secret Algorithm Researchers Used to Break Thousands of RSA Keys

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by schoen on Tuesday January 15, 2019 @03:55PM (#18915112)

This describes research published in 2012 by Arjen Lenstra et al. (https://eprint.iacr.org/2012/064.pdf), which relied on a scalable n-way GCD algorithm that Lenstra's team thought best not to explain to readers (in the hope that the attack wouldn't be quickly replicated for malicious purposes). Coincidentally, another team (Nadia Heninger et al., https://factorable.net/) published extremely similar research in a similar timeframe, without withholding details of that team's GCD calculation approach.

The Heninger et al. paper explains quite a lot about where the underlying problems came from, most often inadequately seeded PRNGs in embedded devices. As the linked article mentions, other subsequent papers have also analyzed variants of this technique and so there's not much secret left about it.

If people are interested in learning about the impact of common factors on the security of RSA, I created a puzzle based on this which you can try out, which also includes an explanation of the issue for programmers who are less familiar with the mathematical context: http://www.loyalty.org/~schoen/rsa/

Notably, my puzzle uses a small set of keys so you can do "easy" pairwise GCD calculations rather than needing an efficient n-way algorithm as described here (which becomes increasingly relevant as the number of keys in question grows).

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by ikeyany on Tuesday January 15, 2019 @06:12PM (#18916600)

I attempted to do your puzzle but the link was blocked by my employer's firewall:

> URL: http://www.loyalty.org/~schoen/rsa/

> Block reason: Violence/Hate/Racism

So... what exactly is loyalty.org all about?

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by casefields on Tuesday January 15, 2019 @06:22PM (#18916693)

"www.loyalty.org itself is the server for the web site of Californians for Academic Freedom, the group I founded to oppose the California loyalty oath, which is still a non-negotiable requirement for anyone who wants to work for the State of California -- including student employees of the University of California. "

http://www.loyalty.org/~schoen/

That's the most controversial thing about the page. In my view it's not a big deal to have that stance but some people don't like others who rock the boat when it comes to the status quo.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by schoen on Tuesday January 15, 2019 @06:43PM (#18916868)

My activism on this issue for the past decade and a half has basically consisted of corresponding for a few minutes each year with some new person who objects to signing the loyalty oath. I doubt that the site blocking has anything to do with this.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by wlll on Wednesday January 16, 2019 @08:29AM (#18920618)

I was curious about the contents and contentions points of the oath so went looking and one of the files you link to is a 404:

http://www.loyalty.org/oath.txt

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by cogburnd02 on Wednesday January 16, 2019 @08:47AM (#18920755)

http://web.archive.org/web/20000831114425/http://www.loyalty...

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by xkcd-sucks on Tuesday January 15, 2019 @11:45PM (#18918286)

Catch-22 should be required reading cf. "The great loyalty oath crusade"

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by schoen on Tuesday January 15, 2019 @06:41PM (#18916851)

I don't know why my web site was categorized that way by your employer's firewall.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by ikeyany on Tuesday January 15, 2019 @06:53PM (#18916948)

Thanks, I'll look into that.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by joering2 on Wednesday January 16, 2019 @12:22AM (#18918446)

Could you tell me the brand? I would like to test few sites that I believe are much worse than loyality.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by dunham on Tuesday January 15, 2019 @10:40PM (#18918059)

I'm guessing it's a false positive from using an IP similar to a sketchy site. It looks like the IP points to Linode.

For what it's worth, I enjoyed the puzzle when I completed it three years ago. A practical exercise cracking the RSA keys followed by a small classic code breaking puzzle.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by inciampati on Tuesday January 15, 2019 @06:16PM (#18916644)

I really doubt that shoen's page is any issue. Perhaps you can get to it in the way back machine.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by semi-extrinsic on Tuesday January 15, 2019 @07:20PM (#18917128)

My experience with these firewalls/blacklists is that they have quite a few random false positives. Requests for fixing them one-by-one seems to be a recurring theme on our company chat.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by ndnxhs on Wednesday January 16, 2019 @04:01AM (#18919286)

I would leave a company that used an internet blocker. They constantly get in the way of real work and benefit no one. The only valid use case I see is attempting to stop idiots downloading malware and installing it on company computers

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by semi-extrinsic on Wednesday January 16, 2019 @05:00AM (#18919549)

In more "traditional" companies that have software dev departments, they are extremely common in my experience, so switching companies wouldn't help much if you're in such a field.

If 90% of the company employees only use IE and MS Word and are actually likely to install malware, and the last 10% are software engineers/data analysts/numerical simulation people, the latter are gonna have to work within/around these types of constraints.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by ndnxhs on Wednesday January 16, 2019 @05:25AM (#18919648)

Part of the reason I dont work at such places. Wouldn't want to be somewhere where I am treated like an idiot.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by semi-extrinsic on Wednesday January 16, 2019 @05:37AM (#18919701)

I guess we all find different optima. To me it's not really being treated like an idiot, it's "we need to have a policy that takes into account that most of the people are idiots, you smart guys work around it if necessary".

I don't know where you work, but off-hand I would postulate that working at "such places" also has advantages over where you work (e.g. better work-life balance, living in an area where property prices are not insane, etc.). As I said, we find different optima in these tradeoffs.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by michaelmrose on Wednesday January 16, 2019 @01:35AM (#18918719)

On a personal device it's reasonable to use a VPN.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by acct1771 on Wednesday January 16, 2019 @02:59AM (#18919056)

On a personal device, it's reasonable to use LTE.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by michaelmrose on Wednesday January 16, 2019 @04:06PM (#18925254)

Not always feasible. Not everyone has a cash to spend on data and lives in an area with good wireless coverage.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by semi-extrinsic on Wednesday January 16, 2019 @04:52AM (#18919504)

It might be the case that some people employ VPN, or SOCKS proxies over ssh to their home computer, or similar schemes. I wouldn't know.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by KwanEsq on Tuesday January 15, 2019 @10:17PM (#18917982)

Maybe a particularly simplistic auto-categoriser mistook the few eighty-eights (88s) on the root page[0] for their use as Nazi symbolism[1]?

[0] http://www.loyalty.org/

[1] https://en.wikipedia.org/w/index.php?title=88_(number)&oldid...

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by kragen on Wednesday January 16, 2019 @03:24PM (#18924736)

For context, Seth Schoen is not only very tolerant, one of the least racist USAns I know, but also Jewish.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by croh on Tuesday January 15, 2019 @11:14PM (#18918188)

mine too interesting. which firewall do your employer use ? here it is sonicwall.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by gtsteve on Tuesday January 15, 2019 @06:15PM (#18916634)

It appears to be a personal website; I believe it is miscategorised.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by swish_bob on Wednesday January 16, 2019 @09:01AM (#18920873)

Nice puzzle. Feels like a good exercise for stretching the brain.

[ Parent | on HN ]

Re:An Almost-Secret Algorithm Researchers Used to Break Thou... by lurkertroll on Tuesday January 15, 2019 @09:15PM (#18917730)

This website does a great job explaining how encryption works and how it's vulnerable to bad RNGs. Well done.

[ Parent | on HN ]