📅 Original date posted:2018-01-09
📝 Original message:On Mon, Jan 8, 2018 at 7:39 AM, Pavol Rusnak via bitcoin-dev <
bitcoin-dev at lists.linuxfoundation.org> wrote:
> On 08/01/18 05:22, Gregory Maxwell wrote:
> >> https://github.com/satoshilabs/slips/blob/master/slip-0039.md
>
>
> > The 16-bit "checksum" based on sha2 seems pretty poor since basing
> > small checksums on a cryptographic hash results in a fairly poor
> > checksum that is surprisingly likely to accept an errored string. Your
> > wordlist is 10 bits and you have much less than 1023*10 bits of input,
> > so you could easily have a 20 bit code (two words) which guaranteed
> > that up to two errored words would always be detected, and probably
> > could choose one which catches three words much more often 1:2^20
> > (sipa's crc tools can help find codes like this).
>
> Originally, we wanted to use 16-bit of CRC32 for checksum, but after the
> discussion with Daan Sprenkels we were suggested to change this for
> cryptographically strong function. The argument was that CRC32 contains
> less entropy and mixing high-entropy data (secret) with low-entropy data
> (checksum) is not a good idea.
>
This entropy argument seems confused. Ignoring constant factors, the
entropy of a checksum is the sum over all possible checksums, i, of
-n_i*log(n_i), where n_i is the number of times the ith checksum occurs
over the space of all possible data being checksummed. In this application
the checksum is being applied to a fixed m-bit blob of uniformly random
data.
The entropy is maximized when every possible checksum occurs equally as
frequently, that is we achieve maximum entropy when all the n_i values are
equal to each other. Any error correcting code worth it's salt will try to
achieve this property because the designers want every checksum value to
have as much error correcting power as every other checksum value. I'm
almost certain that the algebraic properties of your typical error
correcting codes allow you to prove that maximum entropy is perfectly
achieved whenever the data-blob size is at least as large as the checksum
size.
Meanwhile the truncated value of a cryptographic hash function is expected
to be slightly under the maximum entropy value, under the assumption that
the hash function it behaves like a random function.
The main properties of a "strong cryptographic hash function" is that it is
infeasible to find collisions and preimages. However these properties are
lost when you truncate the hash down to 16-bits. At this point is it
entirely feasible to find collisions and preimages.
So using a truncated cryptographic hash function doesn't provide you with
more entropy (and, in fact, probably a sliver less entropy), and doesn't
provide you with any of the befits of strong cryptographic hash function.
> Also, there is an argument between a checksum and ECC. We discussed that
> ECC might not be a good idea, because it helps the attacker to compute
> missing information, while we only want to check for integrity. Also the
> word mnemonic is itself a ECC, because if you see the word "acadornic"
> it is probably the word "academic".
>
Every checksum is error correcting. Given an failed checksum, all you have
to do is search around the space of edits to find the smallest set edits
that yield a valid checksum. With a 2^16 bit checksum one will expect to
find a nearby checksum within 2^16 trails, even when using a truncated hash
function.
What an error-correcting codes gives you isn't the ability to correct
errors, which we have seen is something that all short checksums provide,
rather they provide *guarantees* about the ability to detect (and correct)
certain common classes of errors. For example we can have an ECC that
guarantees to find the error where are word is accidentally written down
twice (see
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015506.html
).
The advice you have been given will only result in losing any guarantees
about detecting common classes or errors; it won't stop attackers from
recovering missing information, and it won't provide a cryptographically
strong function.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180109/5f03431f/attachment.html>;
Russell O'Connor [ARCHIVE] /
npub1dw…8plrw
2023-06-07 18:09:31
in reply to nevent1q…xphr
Author Public Key
npub1dw88wd5gqsqn6ufxhf9h03uk8087l7gfzdtez5csjlt6pupu4pwsj8plrwPublished at
2023-06-07 18:09:31Event JSON
{
"id": "b2af65180ab9189a4d7ebb5e212302e37e499891fd9864a8d60f76b841e18066",
"pubkey": "6b8e77368804013d7126ba4b77c7963bcfeff909135791531097d7a0f03ca85d",
"created_at": 1686161371,
"kind": 1,
"tags": [
[
"e",
"ac3c87f148ca764c85262d935c0d26818cde51a790aa045223a08240c1ff8e91",
"",
"root"
],
[
"e",
"e4988414567638001e263f0d13f086786d3be493cbc603b1d64d731c491ec820",
"",
"reply"
],
[
"p",
"7631397e469f47f3535567311f5f7c17129e0ff2cb253df015e3d92ddfd92c63"
]
],
"content": "📅 Original date posted:2018-01-09\n📝 Original message:On Mon, Jan 8, 2018 at 7:39 AM, Pavol Rusnak via bitcoin-dev \u003c\nbitcoin-dev at lists.linuxfoundation.org\u003e wrote:\n\n\u003e On 08/01/18 05:22, Gregory Maxwell wrote:\n\u003e \u003e\u003e https://github.com/satoshilabs/slips/blob/master/slip-0039.md\n\u003e\n\u003e\n\u003e \u003e The 16-bit \"checksum\" based on sha2 seems pretty poor since basing\n\u003e \u003e small checksums on a cryptographic hash results in a fairly poor\n\u003e \u003e checksum that is surprisingly likely to accept an errored string. Your\n\u003e \u003e wordlist is 10 bits and you have much less than 1023*10 bits of input,\n\u003e \u003e so you could easily have a 20 bit code (two words) which guaranteed\n\u003e \u003e that up to two errored words would always be detected, and probably\n\u003e \u003e could choose one which catches three words much more often 1:2^20\n\u003e \u003e (sipa's crc tools can help find codes like this).\n\u003e\n\u003e Originally, we wanted to use 16-bit of CRC32 for checksum, but after the\n\u003e discussion with Daan Sprenkels we were suggested to change this for\n\u003e cryptographically strong function. The argument was that CRC32 contains\n\u003e less entropy and mixing high-entropy data (secret) with low-entropy data\n\u003e (checksum) is not a good idea.\n\u003e\n\nThis entropy argument seems confused. Ignoring constant factors, the\nentropy of a checksum is the sum over all possible checksums, i, of\n-n_i*log(n_i), where n_i is the number of times the ith checksum occurs\nover the space of all possible data being checksummed. In this application\nthe checksum is being applied to a fixed m-bit blob of uniformly random\ndata.\n\nThe entropy is maximized when every possible checksum occurs equally as\nfrequently, that is we achieve maximum entropy when all the n_i values are\nequal to each other. Any error correcting code worth it's salt will try to\nachieve this property because the designers want every checksum value to\nhave as much error correcting power as every other checksum value. I'm\nalmost certain that the algebraic properties of your typical error\ncorrecting codes allow you to prove that maximum entropy is perfectly\nachieved whenever the data-blob size is at least as large as the checksum\nsize.\n\nMeanwhile the truncated value of a cryptographic hash function is expected\nto be slightly under the maximum entropy value, under the assumption that\nthe hash function it behaves like a random function.\n\nThe main properties of a \"strong cryptographic hash function\" is that it is\ninfeasible to find collisions and preimages. However these properties are\nlost when you truncate the hash down to 16-bits. At this point is it\nentirely feasible to find collisions and preimages.\n\nSo using a truncated cryptographic hash function doesn't provide you with\nmore entropy (and, in fact, probably a sliver less entropy), and doesn't\nprovide you with any of the befits of strong cryptographic hash function.\n\n\n\u003e Also, there is an argument between a checksum and ECC. We discussed that\n\u003e ECC might not be a good idea, because it helps the attacker to compute\n\u003e missing information, while we only want to check for integrity. Also the\n\u003e word mnemonic is itself a ECC, because if you see the word \"acadornic\"\n\u003e it is probably the word \"academic\".\n\u003e\n\nEvery checksum is error correcting. Given an failed checksum, all you have\nto do is search around the space of edits to find the smallest set edits\nthat yield a valid checksum. With a 2^16 bit checksum one will expect to\nfind a nearby checksum within 2^16 trails, even when using a truncated hash\nfunction.\n\nWhat an error-correcting codes gives you isn't the ability to correct\nerrors, which we have seen is something that all short checksums provide,\nrather they provide *guarantees* about the ability to detect (and correct)\ncertain common classes of errors. For example we can have an ECC that\nguarantees to find the error where are word is accidentally written down\ntwice (see\nhttps://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/015506.html\n).\n\nThe advice you have been given will only result in losing any guarantees\nabout detecting common classes or errors; it won't stop attackers from\nrecovering missing information, and it won't provide a cryptographically\nstrong function.\n-------------- next part --------------\nAn HTML attachment was scrubbed...\nURL: \u003chttp://lists.linuxfoundation.org/pipermail/bitcoin-dev/attachments/20180109/5f03431f/attachment.html\u003e",
"sig": "ae7596193f8d57549026baf3f25c0f37cf9656cc0acb72a20914d447874b772812653df155b5139e651f785aa7406e508d3ce8b7641e996646c2ca1e9702a981"
}