[HN Gopher] Milk Sad: Weak Entropy in libbitcoin (bc) seed gener...
___________________________________________________________________
Milk Sad: Weak Entropy in libbitcoin (bc) seed generation
Author : dgrove
Score : 68 points
Date : 2023-08-08 20:14 UTC (2 hours ago)
(HTM) web link (milksad.info)
(TXT) w3m dump (milksad.info)
| RustyRussell wrote:
| Worth noting: libbitcoin is an obscure project with an impressive
| name.
|
| In that it's not used by bitcoind or any wallets I know of: it's
| mainly of interest here because the book Mastering Bitcoin used
| it for examples.
| lrvick wrote:
| It is also of interest because at least ~$1m+ of funds were
| stolen from thousands of wallets made by people that wanted a
| simple and seemingly reputable CLI tool to generate a mnemonic
| and derive addresses for various coins.
| NelsonMinar wrote:
| "On Libbitcoin Explorer 3.x versions, bx seed uses the Mersenne
| Twister pseudorandom number generator (PRNG) initialized with 32
| bits of system time."
|
| That's a hell of an amateur mistake to make. 50/50 odds whether
| it was incompetence or deliberate fraud. Maybe 80/20; that flaw
| is so simple anyone can attack it. Which apparently is happening
| right now. It's much better if your crypto library generates keys
| only you can hack.
| alyandon wrote:
| A non-cryptographic PRNG with a 32 bit seed and yet all the
| other maths/details are correct? I refuse to believe that that
| is anything but deliberate fraud.
| yieldcrv wrote:
| if it's something only you can attack then there is no
| plausible deniability if you become accused as the code
| contributor
| ryanatdistrust wrote:
| To verify, this is something _anyone_ can attack, as was
| proven by our brute force lookup service:
| https://lookup.milksad.info.
| technion wrote:
| Seeing it declared a WONTFIX to me helps answer which of those
| it was. If it was fraud, you'd expect a fake apology and a fix
| at this point.
| nullc wrote:
| Why? The regress is infinite, it's zero information. A
| malicious party can anticipate any public-information
| rational for dismissing their actions and pretend to be
| whatever flavor of fool you might accept.
|
| "Now, a clever man would put the poison into his own goblet,
| because he would know that only a great fool would reach for
| what he was given. I am not a great fool, so I can clearly
| not choose the wine in front of you. But you must have known
| I was not a great fool, you would have counted on it, so I
| can clearly not choose the wine in front of me. ... Because
| iocane comes from Australia, as everyone knows, and Australia
| is entirely peopled with criminals, and criminals are used to
| having people not trust them, as you are not trusted by me,
| so I can clearly not choose the wine in front of you."
| aidenn0 wrote:
| Would a CSPRNG be at all an improvement with only a 32 bit
| seed? Couldn't you still brute force it?
| ryanatdistrust wrote:
| That is correct, you still have 2^32 permutations of possible
| values.
| marginalia_nu wrote:
| Given it's seeded with system time, depending on the
| resolution, that may in practice be as low as tens of
| thousands of possible values (as in time(2) )
| comboy wrote:
| Why is it a mistake?
| wmf wrote:
| As the article explains, 32 bits of entropy isn't enough for
| any cryptographic secret because it can be easily brute-
| forced.
| NelsonMinar wrote:
| Also if it's really the date it's nowhere near 32 bits of
| entropy. I'm guessing you can pretty easily guess to the
| day when a Bitcoin wallet was created, so that's about 16
| bits of entropy. Less if you know the time, possibly 0.
| ryanatdistrust wrote:
| It actually uses the most precise 32 bits of the date, so
| it's any, like, nanosecond between 0 and some other small
| amount of seconds. You can't brute force a wallet by
| knowing _approximately_ when it was made, but you _can_
| brute force _every_ mnemonic if you have the time or a
| bit of cash to throw at a server.
|
| EDIT: It loops around to 0 every 4.something seconds, so
| it's not like everything after 4 is the same key. It's
| just a more random distribution than what you may be
| thinking.
| aidenn0 wrote:
| There is often very low entropy in the lowest few bits of
| system time as well (due to the underlying clock having a
| different resolution than the system call). Given that
| every bit you lose halves the time for a brute-force,
| that's a problem.
| ryanatdistrust wrote:
| The difference between 32 bits and 64 bits is the amount of
| people on Earth compared to (EDIT) the amount of grains of
| sand on Earth. 32 bits is _nothing_ when it comes to entropy,
| and it can take a security researcher (like us) only $100 to
| rent a machine to completely brute force it. Nowadays, only
| values less than 128 or 256 bits (which are _exponentially_
| bigger) are seen as appropriate.
| hashmush wrote:
| Seems a bit overkill with a brand + domain name for every new
| vulnerability.
|
| Don't get me wrong, it's a nice find and all, but I'm really
| distracted by all the fluff.
| tptacek wrote:
| That's on you, though. The name doesn't cost anything, but it
| does make the vulnerability easier to talk about.
| thomastjeffery wrote:
| I suspect the domain literally cost money...
| lrvick wrote:
| It cost me $4 to help get the word out on a bug that is
| being actively exploited right now, stealing valuable
| property. I am good with that.
| lalopalota wrote:
| Where do you buy a $4 domain?
| topato wrote:
| Porkbun? I buy under a dollar domains from them
| frequently
| jnaulty wrote:
| based on the `whois milksad.info` Domain registrar is
| Namecheap :shrug:
| NelsonMinar wrote:
| Eh, let the security consultants have their moment. Also it's a
| great name. "Running bx seed on 3.x versions with a system time
| of 0.0 always generates the following secret: milk sad wage cup
| reward..."
| ryanatdistrust wrote:
| we had so much fun trying to figure out the icon!
| kmeisthax wrote:
| Reminds me of attacks people were running on 'brainwallets' a
| while back - i.e. wallets whose initial key material was just a
| passphrase you'd remember. The idea was that you could keep the
| passphrase stored _nowhere_ and not have to worry about it being
| stolen by... well, any of the 10,000 things out there looking for
| cryptocurrency keys. Of course, there is no way in hell you can
| actually make the human brain store enough entropy perfectly, and
| once people realized that these wallets were crackable, they all
| got drained pretty quick.
|
| Owning Bitcoin is like paying into an involuntary bug bounty
| program. Every time someone finds a bug, your life savings get
| wiped out.
| tomjakubowski wrote:
| You only need a phrase of twelve words from a 2048 word
| dictionary to have 128 bits of entropy. Twelve words is up to
| "Thy kingdom" in the Lord's Prayer, so certainly people are
| able to memorize twelve word phrases or even 24 word phrases
| without too much trouble.
|
| And English is a lot more than 2048 words - so you could
| probably use a shorter phrase and still be fine.
| nullc wrote:
| Unfortunately there is good reason to think that memorability
| and low entropy (against a sufficiently advanced sequence
| generator) are highly related.
| rcoveson wrote:
| The thing about the Lord's Prayer doesn't really follow. If
| you use a grammatically correct and semantically commonplace
| 12 word sequence like that, you surely don't have 128 bits of
| entropy. But the ease of memorization comes almost entirely
| from those attributes!
|
| To get 128 bits of entropy with words, you need to pick about
| thirteen out of a million words--which is on the order of
| _all_ the words in the English language--and give all of them
| equal probability. The sequence needs to be fully random as
| well. What you end up with will surely be easier to memorize
| than a UUID, but substantially more difficult than the start
| of the Lord 's Prayer.
|
| EDIT: Math is wrong, I was thinking 10 bits per million
| instead of 20. So 6-7 words out of a million (whole language)
| or 13 words out of a thousand (very limited subset of the
| language). Point about random selection still stands, but
| it's certainly easier than 13 very uncommon words. Still much
| harder than a realistic sentence of that length, though.
| quonn wrote:
| But the phrases are random, so unlike poems or prayers they
| are difficult to memorize.
| TravelTechGuy wrote:
| Your last sentence should be a t-shirt.
| ajross wrote:
| > Of course, there is no way in hell you can actually make the
| human brain store enough entropy perfectly
|
| Sure there is. Have horse batteries taught us nothing?
|
| https://xkcd.com/936/
|
| Don't confuse key length with entropy. A properly-scaled PBKDF
| remains secure with as little as 48 bits or so. Needless to
| say, though, a 32 bit time value is hardly a properly designed
| key derivation input.
| codetrotter wrote:
| This xkcd comic has been instrumental to me.
|
| I wrote a command-line utility a couple of years ago that I
| use myself regularly to generate secure and memorable
| passwords
|
| https://github.com/ctsrc/Pgen
|
| With this tool you can also see how many bits of entropy the
| passphrase generation settings you are using will result in.
|
| For example, generating a 5 word passphrase using the long
| wordlist pgen -l -n 5
|
| will yield a passphrase like: joyous
| embolism outsider evasion mashed
|
| And when we ask the tool for the entropy with these settings
| pgen -l -n 5 -e
|
| it will tell us: Current settings will
| create passphrases with 64.62 bits of entropy.
|
| And hey, if you have reason to not trust the randomness
| capabilities of the program or your computer guess what :)
|
| My program supports the use of physical dice to generate your
| password.
|
| Have a look, try it out yourselves :D
|
| https://github.com/ctsrc/Pgen
| ryanatdistrust wrote:
| It looks neat, I'll pass this along to the team and take a
| deeper look at it later.
| alchemist1e9 wrote:
| Do you have a reference for large numbers of brain wallets
| being drained? I believe you are repeating a myth/FUD, but I
| might be wrong.
| ryan-c wrote:
| https://www.cs.unm.edu/~vasek/papers/vasekfc16.pdf
|
| Also, there was an ethereum wallet with over 40,000 ETH that
| got drained.
| lostmsu wrote:
| Note: "Libbitcoin" here is a company name, and not a name of the
| core bitcoin library.
|
| Only their products and whoever used them as a 3rd party is
| affected.
| drexlspivey wrote:
| Here's a thread on how bitcoin core generates entropy
| https://twitter.com/raw_avocado/status/1445024873382809604
| Modified3019 wrote:
| Exactly what I came here to find out, thank you.
| tedunangst wrote:
| Weird. I've been assured, repeatedly, that time seeded PRNGs are
| never used for crypto and it's not an issue worth addressing.
| ryanatdistrust wrote:
| As long as people can write code, bugs will exist.
| yieldcrv wrote:
| Are any of the following two things true:
|
| Multi signature addresses mitigate this attack vector?
|
| With the "taproot+schnoor" upgrade last year, it is impossible to
| tell if funds are stored in a single signature vs multi signature
| address?
| lrvick wrote:
| If all the keys were generated with bad entropy, more of them
| is only buying you some obfuscation.
| yieldcrv wrote:
| Generate keys with different apps or methods, for more peace
| of mind
|
| That was one of the goals of initial multisignature
| technology in bitcoin, it was about if one of your devices
| got compromised you could have 2 factor and not approve the
| transaction. People werent thinking about if your private key
| generation was compromised, but it works here too
| ryan-c wrote:
| I wonder whether they modified brainflayer for brute forcing
| this, or if they wrote something from scratch.
| ryanatdistrust wrote:
| We used the broken algorithm from `bx` in a custom Rust program
| to brute force this.
| ryan-c wrote:
| What sort of rate did you get for computing the hashed public
| keys?
| ryanatdistrust wrote:
| I was not involved in that specific aspect, so I can't
| provide accurate information. We may release more
| information later in the future.
| ryan-c wrote:
| 2^32 search space for each set? That seems to imply a
| little under 2,000 keys per second?
| ryanatdistrust wrote:
| My numbers are very rough estimates and not good enough
| to do work on. More accurate information may be made
| public later.
___________________________________________________________________
(page generated 2023-08-08 23:00 UTC)