Author Topic: Solution found to Ron Rivest's LCS35 timelock challenge  (Read 10301 times)

0 Members and 1 Guest are viewing this topic.

Offline TacticalCoder

  • Thread Starter
  • Posts: 526
Solution found to Ron Rivest's LCS35 timelock challenge
« on: Tue, 28 May 2019, 15:48:39 »
Hey all,

now that the dust settled a bit I've got some time to post about it and it's geeky enough for "Other geeky stuff"...

Some may have seen it as it was frontpage on Hacker News for quite a few hours (2nd position actually) and was in the news here and there (it was even on TV).


Long story short: in 1999 the MIT organized a big party to celebrate the 35th anniversay of the Laboratory of Computer Science (LCS, now called CSAIL since it merged with the AI lab). During this event several computing and Internet pionneers did put stuff (papers, discs, PCBs, ...) inside a "time capsule" (a big lead bag made by architect Frank Gehry), including Tim Berners Lee, Bill Gates, the VisiCalc authors (the first spreadsheet program ever), Metcalfe (Ethernet), the first RSA paper and many other insane things.


The capsule was to be opened in 2034 or when someone would find the answer to a cryptographic challenge Ron Rivest (the 'R' from RSA) created back in 1999 and which was supposed to take 35 years before being solvable, taking Moore's Law into account.


Incredibly enough Rivest didn't hear anything about this puzzle for 20 years (he mentioned it himself several times and LCS35 was mentioned on forums / blogs / tweets etc. but nobody contacted Rivest about it for 20 years) and then... Within 24 hours he got an email from a team announcing they'd have the solution withing a month and an email by me saying I had the solution.


So yeah, I was the first to find the solution, about 6 weeks ago.  I got invited for one week at the MIT's CSAIL to meet Ron Rivest and talk in public (room was full, so there was an "overflow room" where the talks were streamed) about how I solved LCS35.


I got to spend a few hours with Ron Rivest, spent one hour in Sussman's office who dedicated me a copy of SICP (aka "the purple book") and by chance Abelson was in his office so he signed the book too (!), met amazing people the whole week on campus.  I also met the team who configured a FPGA running a custom algorithm to solve LCS35 in two months. My whole week in Cambridge was crazy.


The little Wikipedia page about LCS35:

https://en.wikipedia.org/wiki/LCS35

An article about the solution (with a pic of me in front of my HHKB Pro JP and 38" curved screen):

https://www.boston.com/news/local-news/2019/05/21/bernard-fabrot-mit-puzzle

Also RIP my 4 years old core i7 6700 (non K) CPU: the time capsule was opened, all the items pulled out, then all pull back in and new ones added... Including my core i7 6700.  It was the 2nd best CPU for single-core performance back when I bought it (with only the 6700K better but I took a 6700 to get slightly lower max TDP and less noise) and single-core spec is all that mattered to solve LCS35 (which is why I bought that CPU back then).  Now ofc there are better ones.  So yup, made a gift to the MIT's CSAIL: my trusty core i7-6700 who ran one core at 100% 3.9 to 4.0 Ghz nearly non stop for 3.3 years has earned a very long rest alongside amazing artefacts.

Hope you like the story,

« Last Edit: Tue, 28 May 2019, 15:54:52 by TacticalCoder »
HHKB Pro JP (daily driver) -- HHKB Pro 2 -- Industrial IBM Model M 1395240-- NIB Cherry MX 5000 - IBM Model M 1391412 (Swiss QWERTZ) -- IBM Model M 1391403 (German QWERTZ) * 2 -- IBM Model M Ambra -- Black IBM Model M M13 -- IBM Model M 1391401 -- IBM Model M 139? ? ? *2 -- Dell AT102W -- Ergo (split) SmartBoard (white ALPS apparently)

Offline TacticalCoder

  • Thread Starter
  • Posts: 526
Re: Solution found to Ron Rivest's LCS35 timelock challenge
« Reply #1 on: Tue, 28 May 2019, 15:53:23 »
Oh and it's very grossly like RSA... You know one number which is the product of two huge primes, primes which are unknown. The secret message says: "!!!  Happy Birthday LCS !!!" and contains a seed allowing to find one of the two factors (and hence the second too).  I now uploaded the factors to factordb.com:

http://factordb.com/index.php?id=1100000000556764164
HHKB Pro JP (daily driver) -- HHKB Pro 2 -- Industrial IBM Model M 1395240-- NIB Cherry MX 5000 - IBM Model M 1391412 (Swiss QWERTZ) -- IBM Model M 1391403 (German QWERTZ) * 2 -- IBM Model M Ambra -- Black IBM Model M M13 -- IBM Model M 1391401 -- IBM Model M 139? ? ? *2 -- Dell AT102W -- Ergo (split) SmartBoard (white ALPS apparently)

Offline TacticalCoder

  • Thread Starter
  • Posts: 526
Re: Solution found to Ron Rivest's LCS35 timelock challenge
« Reply #2 on: Fri, 14 June 2019, 07:46:24 »
Turns out it was a major PITA to find a CPU compatible with my mobo to replace the 6700 I put inside the capsule. My mobo takes 6th and 7th gen but 7th gen only if I patch the firmware which, on this model, cannot be done without a CPU in it. And because I'm in the middle of nowhere and had issue with my credit cards, it's been complicated to get a "new" CPU.

Ended up finding a 6700K to replace my 6700.  This machine which served me well for about 4 years is probably going to become a server in my little homelab (for software R&D purposes) now while I may build one of these new fancy Ryzen 3000 thinggies: they seem just too good to be true (60 MB L3 cache on a "consumer" CPU: ffs that's amazing).
HHKB Pro JP (daily driver) -- HHKB Pro 2 -- Industrial IBM Model M 1395240-- NIB Cherry MX 5000 - IBM Model M 1391412 (Swiss QWERTZ) -- IBM Model M 1391403 (German QWERTZ) * 2 -- IBM Model M Ambra -- Black IBM Model M M13 -- IBM Model M 1391401 -- IBM Model M 139? ? ? *2 -- Dell AT102W -- Ergo (split) SmartBoard (white ALPS apparently)

Offline SpAmRaY

  • NOT a Moderator
  • * Certified Spammer
  • Posts: 14667
  • Location: ¯\(°_o)/¯
  • because reasons.......
Re: Solution found to Ron Rivest's LCS35 timelock challenge
« Reply #3 on: Fri, 14 June 2019, 07:56:19 »
This is some seriously geeky stuff. Congrats!



Sent from my SM-G930V using Tapatalk



Offline JP

  • Posts: 359
  • Location: Indianapolis, IN ander, our true elevated elder.
Re: Solution found to Ron Rivest's LCS35 timelock challenge
« Reply #5 on: Fri, 14 June 2019, 13:37:28 »
Oh wow I read about how this was broken using desktop hardware I think a few weeks ago somewhere. This is awesome man and even better it was Geekhacker  :thumb:
About Me | The Collection
Therapy is expensive so I buy keyboards and bike parts.

Offline TacticalCoder

  • Thread Starter
  • Posts: 526
Re: Solution found to Ron Rivest's LCS35 timelock challenge
« Reply #6 on: Sat, 15 June 2019, 18:29:53 »
Oh wow I read about how this was broken using desktop hardware I think a few weeks ago somewhere. This is awesome man and even better it was Geekhacker  :thumb:

Ah ah thanks to all of you!

Consumer hardware indeed but the problem is sequential on purpose: back when I bought the chip I think it was the second best for single-core perfs so server hardware or say Xeon workstations wouldn't help much (as far as I know). I considered upgrading to a 7th gen than 8th gen CPU to finish a bit faster but ended doing the entire computation on my 6th gen i7.

What I didn't know: at least four of us were computing towards a solution... There were two different teams with FPGAs (one finished three weeks after me and the other two months after me) but also someone else with a big AMD CPU (don't remember the exact model): he was 56% into the computation!

The FPGA solutions are more impressive (and about 15x faster) but I got lucky in realizing quite early that the problem was actually solvable in a reasonable amount of time.

Glad you guys like it that a HNer solved it! : )
HHKB Pro JP (daily driver) -- HHKB Pro 2 -- Industrial IBM Model M 1395240-- NIB Cherry MX 5000 - IBM Model M 1391412 (Swiss QWERTZ) -- IBM Model M 1391403 (German QWERTZ) * 2 -- IBM Model M Ambra -- Black IBM Model M M13 -- IBM Model M 1391401 -- IBM Model M 139? ? ? *2 -- Dell AT102W -- Ergo (split) SmartBoard (white ALPS apparently)

Offline Sintpinty

  • Carbon Based Life Form
  • Posts: 1667
  • Location: A can of beans in the cupboard
  • she/her/they/them/any except he him
    • My Roblox Profile
Re: Solution found to Ron Rivest's LCS35 timelock challenge
« Reply #7 on: Mon, 17 June 2019, 08:41:45 »
I'm not even smart enough to solve that... but anyways congrats.
« Last Edit: Mon, 17 June 2019, 08:43:46 by Sintpinty »

Offline TacticalCoder

  • Thread Starter
  • Posts: 526
Re: Solution found to Ron Rivest's LCS35 timelock challenge
« Reply #8 on: Tue, 18 June 2019, 14:42:56 »
I'm not even smart enough to solve that... but anyways congrats.

I'm a software developer, not a cryptographer. The math behind the problem are relatively simple: it's a trapdoor function (not unlike the RSA one)
 where there's an asymmetry between the time it takes to encrypt (when knowing two big prime numbers) and the time it takes to "break" (or "solve" in this case) without knowing these two primes (all you know is the factor of these two huge primes and, well, factorization is a very hard thing to do once numbers gets big).

No need to be smart: this was only a few lines of code. What was necessary was... Patience! (and realizing the problem could now be solved in a "reasonable" amount of time when using a carefully optimized library for these kind of computation).
 
HHKB Pro JP (daily driver) -- HHKB Pro 2 -- Industrial IBM Model M 1395240-- NIB Cherry MX 5000 - IBM Model M 1391412 (Swiss QWERTZ) -- IBM Model M 1391403 (German QWERTZ) * 2 -- IBM Model M Ambra -- Black IBM Model M M13 -- IBM Model M 1391401 -- IBM Model M 139? ? ? *2 -- Dell AT102W -- Ergo (split) SmartBoard (white ALPS apparently)