7 ms·

Shamir Secret Sharing

238 points by yankcrime 3y ago

threesevenths 3y ago
This story has been posted numerous times in the last fortnight. It’s a great story but certainly undeserving of a reread
- dxdm 3y ago
  I read HN almost every day, and this is the first time I've seen the link. I'm glad it was posted again.
  - threesevenths 3y ago
    It is a good story.
BtM909 3y ago
See previous discussion(s): https://news.ycombinator.com/item?id=36941720 https://news.ycombinator.com/item?id=36941720
- mdaniel 3y ago
  yeah, it evidently got posted on some social media because it's been just rampantly resubmitted https://news.ycombinator.com/from?site=max.levch.in https://news.ycombinator.com/from?site=max.levch.in I really wish HN had the mildest of dupe checking, as anyone who does care about the topics of these repeated reposts has to go and read all the different threads
NovemberWhiskey 3y ago
>original news of our move to the US was delivered to them via a posted letter, snail mail, not FidoNet email! netmail, not email :-) As the knower of the code, for the safe, in the escorted-only data center, that contains one of our Vault key shares, this story resonates.
londons_explore 3y ago
Printed out the master key and stored it in a safe... Wonder if that printer kept a copy...?
- AstralStorm 3y ago
  Better yet, wonder if someone can steal that safe, open it, then replace it with an identical looking one with the same note? Two words: tamper seals An envelope is easily steamed open. And you better hope nobody bypasses the alarm. Or you won't know to check the seals until it's way too late.
  - antran22 3y ago
    It all boil down to trust. He gave it to somebody he trust, who also have their stake in PayPal. If you couldn't even trust the General Legal Counsel of your company, a secrets key might not be the thing you needed to worry about then.
    - knallfrosch 3y ago
      This. You could tank the company by stealing their funds or simply burning the secret-storing computers down
    - bombcar 3y ago
      Risk mitigation is always about mitigating- making something harder or more impossible than something else. Nothing is perfect but some things are better.
      - antran22 3y ago
        But to what end? What more can you do with a printed envelop? ROT13 or Vignère that piece of text? Then write it with the Dancing Men alphabet? The point is, you can only mitigate so much before it become an exercise in futility. The general counsel, if anybody, is the person that can actually bankrupt your company and get some nice money for himself using some legal tomfoolery. I doubt that if that was his intention, trying to decode a piece of base64 for a private key of the database would be the course of action that he would take. The author was in a (then) startup. He had a sensitive document. He asked the Legal Counsel to keep hold of it and shred it after 1 days. And then forgot about it and went on and built more measure to defend against hacker, which is the more important threat actor here. Know your threat model and expend your/your company limited resource on the things that matter.
AstralStorm 3y ago
Oh boy, one of them classic stories of "we accidentally pushed a development setup into production". What's worse, partially.
- Hendrikto 3y ago
  Did you read the article? There was nothing accidental about this. It was done with a lot of planning and premeditation.
  - AstralStorm 3y ago
    There was no testing. No staging setup. So, premeditated or not, it counts as pushing development code into production. The accidentally part I believe is because someone didn't know any better.
    - striking 3y ago
      Not every company has a staging environment...
      - lmm 3y ago
        As the saying goes, everyone has a test environment, some are lucky enough to have a separate production environment.
      - dcminter 3y ago
        Particularly since, by my recollection, 20 years ago a separate staging environment was the exception not the rule.
  - Cthulhu_ 3y ago
    The oversight is that they developed and tested it on Linux, created the file on Linux as well, but used it on Solaris, using an operating system tool to enter the password that had different behaviour on Solaris (stripping anything beyond 8 characters in length because... nobody needs long passwords, right?). It still happens today though, and subtle differences between computers or e.g. CPU architectures can and will still occur. It's really difficult or cost prohibitive to set up a DTAP or similar where every step is production-like; I can imagine it's similarly complex on modern day distributed systems / microservices.
s1mplicissimus 3y ago
umm so he had the master key printed out as backup anyway so there was never really any danger if i read correctly. clickbait? > Ha. I forgot all about it, but in a bout of “what if it doesn’t work” paranoia, I printed out the base64-encoded master key when we had generated it the night before, stuffed it into an envelope, and gave it to John for safekeeping.
- mmmmmmtoes 3y ago
  [dead]
- nailer 3y ago
  That's correct. But also in his stress, he forgot about this. It's a good lesson about how stress can make people do irrational things, like forget the backup they just made.
numair 3y ago
Oh! We are finally going to talk about how PayPal was utterly owned by Russian cyber gangs that made a mockery of the idea that these guys were fraud detection geniuses? checks article Oh, wait, nevermind. More “folklore.”
- KaiserPro 3y ago
  [citation needed] I'd totally read that, are there any articles?
croes 3y ago
Always test with real values even passwords
- kedean 3y ago
  I dont think that would have helped, half the issue was mixing environments. The master key was generated on Linux, where the passphrases weren't truncated, but it was being used on Solaris where they were. If it had been generated on Solaris or used in Linux the problem wouldn't be there. To find this in testing, you'd have to predict that "data being generated one place and used on another" could be a vector for bugs, and that's not necessarily obvious
  - hutzlibu 3y ago
    "you'd have to predict that "data being generated one place and used on another" could be a vector for bugs, and that's not necessarily obvious" It seems you never had to deal with file encodings? And windows upper lowercase does not matter, compared to linux where it does matter? But yes, obvious was none of that to me, I naivly assumed, data should be just data, until I change it. Like they did.
nailer 3y ago
> Solaris had a “special feature”: any passphrase entered that was longer than 8 characters long was automatically reduced to that length anyway. Solaris is known for having stupid defaults. I once had a box refuse to boot because the whitespace in a config file used tabs rather than spaces.
testemailfordg2 3y ago
Was just reading about this SSS technique yesterday and now its on HN
_xivi 3y ago
Out of curiosity, How is this post not a [dupe] and managed to reach the front page even though it had its fair share not even 10 days ago
- ergl 3y ago
  The URL is different, so it probably slipped under the dupe radar
- distcs 3y ago
  Probably not enough people have flagged it as [dupe]?
deleted 3y ago
[deleted]
seniorThrowaway 3y ago
this brings up old memories of being bitten sometime by this Solaris "feature" although it's been too many years to remember the exact details. It was one of those things that made me realize Linux was actually a much more usable system from a day to day admin point of view, along with package managers. Edit: another one was Solaris defaulting to the obsolete unix crypt function based on the Enigma machine
nickdothutton 3y ago
As soon as getpass was mentioned, I knew. It’s worth reminding people that in these matters, print on paper is a weapon, know when to use it.
EGreg 3y ago
While it’s exciting to read this kind of stuff, and I am glad to see a fellow Soviet emigre come and found a company in the Valley, I have to comment on just how much control is centralized in the hands of a few people, that millions of people come to trust with their data and their money! This is essential commentary to Shamir Secret Sharing, because it requires a trusted dealer, unlike BLS and other bilinear technqiues. Look at this: Whatever key that was, it wasn’t the one I generated the day before: only one copy existed, the one I copied to cryptoserv from my computer the night before. Zero copies existed now. Not only that, the push script appears to have also wiped out the backup of the old key, so the database backups we have encrypted with the old key are likely useless. So with SSS just have to take his word for it, that he didn’t have a copy of the key back on his computer. Zero copies existed? It’s not like he made another copy of it? Surely he is a reliable narrator and we can trust that at least, right? Actually, NOPE: A few hours later, John, our General Counsel, stopped by my cubicle to ask me something. The day before I apparently gave him a sealed envelope and asked him to store it in his safe for 24 hours without explaining myself. He wanted to know what to do with it now that 24 hours have passed. Ha. I forgot all about it, but in a bout of “what if it doesn’t work” paranoia, I printed out the base64-encoded master key when we had generated it the night before, stuffed it into an envelope, and gave it to John for safekeeping. We shredded it together without opening and laughed about what would have never actually been a company-ending event. So the lawyer could have conceivably hired someone to break into the database, steal credit card numbers and salami-slice some value for years, or launch one big attack on the entire database: https://en.wikipedia.org/wiki/Salami_slicing_tactics https://en.wikipedia.org/wiki/Salami_slicing_tactics Having ONE SET OF KEYS or passwords to access THE ENTIRE DATABASE is the epitome of the whole Digital Feudalism that we have today! But that’s what we have in Web2. Sam Bankman Fried is just one example. This is where Web3 is so different. Everyone has their own keys, and they can only do what the are allowed to by the smart contract code. You reduce the attack surface massively. You reduce the need for celebirties like Max Levchin, and his stories, as much as I like them. Some people on HN might dislike Web3 and smart contracts, and I do agree that blockchains arent a very efficient technology for implementing them, but the idea of being able to trust the code is crucial for our society. Otherwise, the closest we can get to it is this: https://signal.org/blog/private-contact-discovery/ https://signal.org/blog/private-contact-discovery/ In an age where Google wants to implement attestations of CLIENTS in Chrome, we as a society should be demanding the other way: proving that the CODE AND DATA cannot be tampered with. SGX extensions are far worse than smart contracts to secure large amounts of value, whether it’s currency balances, votes, or other data. Anyway, for the crypto side I will just say that BLS signatures are far superior to SSS. I mean cryprography when I say crypto. It has NOTHING to do with blockchain, but rather with generation of private keys and verifying transactions that were posted to some decentralized network. Use BLS. SSS is outdated.
tonicanada 3y ago
I found this topic so interesting that I wrote an article about it! https://medium.com/gitconnected/sharing-a-secret-with-polynomial-interpolation-657d2ab1d307 https://medium.com/gitconnected/sharing-a-secret-with-polyno...

238 points by yankcrime 3y ago

This story has been posted numerous times in the last fortnight. It’s a great story but certainly undeserving of a reread

dxdm 3y ago
I read HN almost every day, and this is the first time I've seen the link. I'm glad it was posted again.
- threesevenths 3y ago
  It is a good story.

BtM909 3y ago

See previous discussion(s): https://news.ycombinator.com/item?id=36941720 https://news.ycombinator.com/item?id=36941720

mdaniel 3y ago
yeah, it evidently got posted on some social media because it's been just rampantly resubmitted https://news.ycombinator.com/from?site=max.levch.in https://news.ycombinator.com/from?site=max.levch.in I really wish HN had the mildest of dupe checking, as anyone who does care about the topics of these repeated reposts has to go and read all the different threads

NovemberWhiskey 3y ago

>original news of our move to the US was delivered to them via a posted letter, snail mail, not FidoNet email! netmail, not email :-) As the knower of the code, for the safe, in the escorted-only data center, that contains one of our Vault key shares, this story resonates.

londons_explore 3y ago

Printed out the master key and stored it in a safe... Wonder if that printer kept a copy...?

AstralStorm 3y ago
Better yet, wonder if someone can steal that safe, open it, then replace it with an identical looking one with the same note? Two words: tamper seals An envelope is easily steamed open. And you better hope nobody bypasses the alarm. Or you won't know to check the seals until it's way too late.
- antran22 3y ago
  It all boil down to trust. He gave it to somebody he trust, who also have their stake in PayPal. If you couldn't even trust the General Legal Counsel of your company, a secrets key might not be the thing you needed to worry about then.
  - knallfrosch 3y ago
    This. You could tank the company by stealing their funds or simply burning the secret-storing computers down
  - bombcar 3y ago
    Risk mitigation is always about mitigating- making something harder or more impossible than something else. Nothing is perfect but some things are better.
    - antran22 3y ago
      But to what end? What more can you do with a printed envelop? ROT13 or Vignère that piece of text? Then write it with the Dancing Men alphabet? The point is, you can only mitigate so much before it become an exercise in futility. The general counsel, if anybody, is the person that can actually bankrupt your company and get some nice money for himself using some legal tomfoolery. I doubt that if that was his intention, trying to decode a piece of base64 for a private key of the database would be the course of action that he would take. The author was in a (then) startup. He had a sensitive document. He asked the Legal Counsel to keep hold of it and shred it after 1 days. And then forgot about it and went on and built more measure to defend against hacker, which is the more important threat actor here. Know your threat model and expend your/your company limited resource on the things that matter.

AstralStorm 3y ago

Oh boy, one of them classic stories of "we accidentally pushed a development setup into production". What's worse, partially.

Hendrikto 3y ago
Did you read the article? There was nothing accidental about this. It was done with a lot of planning and premeditation.
- AstralStorm 3y ago
  There was no testing. No staging setup. So, premeditated or not, it counts as pushing development code into production. The accidentally part I believe is because someone didn't know any better.
  - striking 3y ago
    Not every company has a staging environment...
    - lmm 3y ago
      As the saying goes, everyone has a test environment, some are lucky enough to have a separate production environment.
    - dcminter 3y ago
      Particularly since, by my recollection, 20 years ago a separate staging environment was the exception not the rule.
- Cthulhu_ 3y ago
  The oversight is that they developed and tested it on Linux, created the file on Linux as well, but used it on Solaris, using an operating system tool to enter the password that had different behaviour on Solaris (stripping anything beyond 8 characters in length because... nobody needs long passwords, right?). It still happens today though, and subtle differences between computers or e.g. CPU architectures can and will still occur. It's really difficult or cost prohibitive to set up a DTAP or similar where every step is production-like; I can imagine it's similarly complex on modern day distributed systems / microservices.

s1mplicissimus 3y ago

umm so he had the master key printed out as backup anyway so there was never really any danger if i read correctly. clickbait? > Ha. I forgot all about it, but in a bout of “what if it doesn’t work” paranoia, I printed out the base64-encoded master key when we had generated it the night before, stuffed it into an envelope, and gave it to John for safekeeping.

mmmmmmtoes 3y ago
[dead]
nailer 3y ago
That's correct. But also in his stress, he forgot about this. It's a good lesson about how stress can make people do irrational things, like forget the backup they just made.

numair 3y ago

Oh! We are finally going to talk about how PayPal was utterly owned by Russian cyber gangs that made a mockery of the idea that these guys were fraud detection geniuses? checks article Oh, wait, nevermind. More “folklore.”

KaiserPro 3y ago
[citation needed] I'd totally read that, are there any articles?

croes 3y ago

Always test with real values even passwords

kedean 3y ago
I dont think that would have helped, half the issue was mixing environments. The master key was generated on Linux, where the passphrases weren't truncated, but it was being used on Solaris where they were. If it had been generated on Solaris or used in Linux the problem wouldn't be there. To find this in testing, you'd have to predict that "data being generated one place and used on another" could be a vector for bugs, and that's not necessarily obvious
- hutzlibu 3y ago
  "you'd have to predict that "data being generated one place and used on another" could be a vector for bugs, and that's not necessarily obvious" It seems you never had to deal with file encodings? And windows upper lowercase does not matter, compared to linux where it does matter? But yes, obvious was none of that to me, I naivly assumed, data should be just data, until I change it. Like they did.

nailer 3y ago

> Solaris had a “special feature”: any passphrase entered that was longer than 8 characters long was automatically reduced to that length anyway. Solaris is known for having stupid defaults. I once had a box refuse to boot because the whitespace in a config file used tabs rather than spaces.

testemailfordg2 3y ago

Was just reading about this SSS technique yesterday and now its on HN

_xivi 3y ago

Out of curiosity, How is this post not a [dupe] and managed to reach the front page even though it had its fair share not even 10 days ago

ergl 3y ago
The URL is different, so it probably slipped under the dupe radar
distcs 3y ago
Probably not enough people have flagged it as [dupe]?

deleted 3y ago

[deleted]

seniorThrowaway 3y ago

this brings up old memories of being bitten sometime by this Solaris "feature" although it's been too many years to remember the exact details. It was one of those things that made me realize Linux was actually a much more usable system from a day to day admin point of view, along with package managers. Edit: another one was Solaris defaulting to the obsolete unix crypt function based on the Enigma machine

nickdothutton 3y ago

As soon as getpass was mentioned, I knew. It’s worth reminding people that in these matters, print on paper is a weapon, know when to use it.

EGreg 3y ago

While it’s exciting to read this kind of stuff, and I am glad to see a fellow Soviet emigre come and found a company in the Valley, I have to comment on just how much control is centralized in the hands of a few people, that millions of people come to trust with their data and their money! This is essential commentary to Shamir Secret Sharing, because it requires a trusted dealer, unlike BLS and other bilinear technqiues. Look at this: Whatever key that was, it wasn’t the one I generated the day before: only one copy existed, the one I copied to cryptoserv from my computer the night before. Zero copies existed now. Not only that, the push script appears to have also wiped out the backup of the old key, so the database backups we have encrypted with the old key are likely useless. So with SSS just have to take his word for it, that he didn’t have a copy of the key back on his computer. Zero copies existed? It’s not like he made another copy of it? Surely he is a reliable narrator and we can trust that at least, right? Actually, NOPE: A few hours later, John, our General Counsel, stopped by my cubicle to ask me something. The day before I apparently gave him a sealed envelope and asked him to store it in his safe for 24 hours without explaining myself. He wanted to know what to do with it now that 24 hours have passed. Ha. I forgot all about it, but in a bout of “what if it doesn’t work” paranoia, I printed out the base64-encoded master key when we had generated it the night before, stuffed it into an envelope, and gave it to John for safekeeping. We shredded it together without opening and laughed about what would have never actually been a company-ending event. So the lawyer could have conceivably hired someone to break into the database, steal credit card numbers and salami-slice some value for years, or launch one big attack on the entire database: https://en.wikipedia.org/wiki/Salami_slicing_tactics https://en.wikipedia.org/wiki/Salami_slicing_tactics Having ONE SET OF KEYS or passwords to access THE ENTIRE DATABASE is the epitome of the whole Digital Feudalism that we have today! But that’s what we have in Web2. Sam Bankman Fried is just one example. This is where Web3 is so different. Everyone has their own keys, and they can only do what the are allowed to by the smart contract code. You reduce the attack surface massively. You reduce the need for celebirties like Max Levchin, and his stories, as much as I like them. Some people on HN might dislike Web3 and smart contracts, and I do agree that blockchains arent a very efficient technology for implementing them, but the idea of being able to trust the code is crucial for our society. Otherwise, the closest we can get to it is this: https://signal.org/blog/private-contact-discovery/ https://signal.org/blog/private-contact-discovery/ In an age where Google wants to implement attestations of CLIENTS in Chrome, we as a society should be demanding the other way: proving that the CODE AND DATA cannot be tampered with. SGX extensions are far worse than smart contracts to secure large amounts of value, whether it’s currency balances, votes, or other data. Anyway, for the crypto side I will just say that BLS signatures are far superior to SSS. I mean cryprography when I say crypto. It has NOTHING to do with blockchain, but rather with generation of private keys and verifying transactions that were posted to some decentralized network. Use BLS. SSS is outdated.

tonicanada 3y ago

I found this topic so interesting that I wrote an article about it! https://medium.com/gitconnected/sharing-a-secret-with-polynomial-interpolation-657d2ab1d307 https://medium.com/gitconnected/sharing-a-secret-with-polyno...