Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [140.211.166.137]) by lists.linuxfoundation.org (Postfix) with ESMTP id E90CBC002D for ; Sat, 9 Jul 2022 22:21:44 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id CAE12419DE for ; Sat, 9 Jul 2022 22:21:44 +0000 (UTC) DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org CAE12419DE Authentication-Results: smtp4.osuosl.org; dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com header.a=rsa-sha256 header.s=20210112 header.b=YlVSBWYu X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -2.098 X-Spam-Level: X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9t2ei0KqJ1iU for ; Sat, 9 Jul 2022 22:21:43 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.8.0 DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 865334188A Received: from mail-pj1-x102e.google.com (mail-pj1-x102e.google.com [IPv6:2607:f8b0:4864:20::102e]) by smtp4.osuosl.org (Postfix) with ESMTPS id 865334188A for ; Sat, 9 Jul 2022 22:21:43 +0000 (UTC) Received: by mail-pj1-x102e.google.com with SMTP id t5-20020a17090a6a0500b001ef965b262eso1754041pjj.5 for ; Sat, 09 Jul 2022 15:21:43 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=+3VbEgVtF2X30KkT1WbIMpMVuLkOmqbXlJtApLiX+xA=; b=YlVSBWYuEIa7aXRYwIp78vQbry1uGK2A8abIbiJbhMxRAcfFUQFpj9IUzD1pVtmf/y gQdWX1XmmSnZqTJUPlxj7r0H2kG+gNVRJC4QIblvC2EnijuuCWpkGZNLSSLAqxXsTKrP xTjyWH2EImFQPRQ3NbEO3E+/PU5Y531Nb5mmKFC+XP3GS0YMq3RGlLTxh/ngxC4cCyg1 /Jye49lNhz9FYg79fzqYB+c9ChukFcXAsdocZEYXn7q5FqEfaqtsJGXSoOEPN0wkLriv X/Mge9y0mwdetyZECzIEg/uOvEqZs63r4zLWPqsAhI9CMOiSiJAd9uS+l3nNc6/RbzM2 WgzA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=+3VbEgVtF2X30KkT1WbIMpMVuLkOmqbXlJtApLiX+xA=; b=Trs45gnkZLNuz4X6xijtvEbwaryNgOOBPU3TQtA+5vbk/jn9Qq//BG0LS7PuUt0wda JuMXpHoJmDSMbOnWUkRMFXvpufCGIcLfoaRIGpSP+xSyUgKZhtq8H8ag7rxuwai3maEG Bt7LWg0PeGozVEFAx5IJmr2w9isaaQ5IfAfwiMYtnk2fQyvpb2dXUr/d9KTrZhamhjDf +uOSsgHRhDvWR2VV3v+JbbdPOaDx8t0qRrcZHibZnrBNMnuzM4d93KSmeVP4poKpQQiC SpKDxstE2YwnFXWIgKX43ezSw1ssutgdLIEIhE9yjaXrWpbml5ryPsKankX/DKmVolfS ippA== X-Gm-Message-State: AJIora/arO1897y0JCX+fJySeIBWAM01EnBVZQk6KO8w/pSN/1S1cGJy b/sunGD/byl2Yfqfs5X29hJfLszSQ2sC8yxioOsg/5lLRJhdzw== X-Google-Smtp-Source: AGRyM1scFMMoIG8XC52Jl40cjifuTBVQ1IoHu7cvk2W9Mr252bFsVQi30fzRfWldBzTOj3vImijy3gqbfCUZOLU0QPE= X-Received: by 2002:a17:903:183:b0:16a:5c43:9a9c with SMTP id z3-20020a170903018300b0016a5c439a9cmr10521536plg.153.1657405302650; Sat, 09 Jul 2022 15:21:42 -0700 (PDT) MIME-Version: 1.0 References: <3D3BFE9C-CFF3-49FF-840F-063B52C69A42@voskuil.org> <164256450-0ee6752f92c0be297952fc72b59076df@pmq5v.m5r2.onet> In-Reply-To: From: James MacWhyte Date: Sun, 10 Jul 2022 00:21:16 +0200 Message-ID: To: Zac Greenwood Content-Type: multipart/alternative; boundary="000000000000503cb105e366bef7" Cc: Bitcoin Protocol Discussion Subject: Re: [bitcoin-dev] No Order Mnemonic X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Sat, 09 Jul 2022 22:21:45 -0000 --000000000000503cb105e366bef7 Content-Type: text/plain; charset="UTF-8" Thanks, Zac! I indeed did get the napkin math very wrong. I now get around 10^30 total possible phrases, which would take an impossibly long time to brute force. So, it is less entropy but probably still sufficient for low-stakes usage. James On Sat, Jul 9, 2022 at 10:31 PM Zac Greenwood wrote: > Sorting a seed alphabetically reduces entropy by ~29 bits. > > A 12-word seed has (12, 12) permutations or 479 million, which is ln(469m) > / ln(2) ~= 29 bits of entropy. Sorting removes this entropy entirely, > reducing the seed entropy from 128 to 99 bits. > > Zac > > > On Fri, 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev < > bitcoin-dev@lists.linuxfoundation.org> wrote: > >> >> What do you do if the "first" word (of 12), happens to be the last word >>> in the list alphabetically? >>> >> >> That couldn't happen. If one word is the very last from the wordlist, it >> would end up at the end of your mnemonic once you rearrange your 12 words >> alphabetically. >> >> However! >> >> (@vjudeu) Choosing 11 random words and then sorting them alphabetically >> before assigning a checksum would reduce entropy considerably. If you think >> about it, to bruteforce the entire keyspace one would only need to come up >> with every possible combination of 11 words + 1 checksum. I'm not the best >> at napkin math, but I think that leaves you with around 10 trillion >> combinations, which would only take a couple months to exhaust with >> hardware that can do 1 million guesses per second. >> >> >> James >> _______________________________________________ >> bitcoin-dev mailing list >> bitcoin-dev@lists.linuxfoundation.org >> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev >> > --000000000000503cb105e366bef7 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Thanks, Zac!

I indeed did get the napkin math very = wrong. I now get around 10^30 total possible phrases, which would take an i= mpossibly long time to brute force. So, it is less entropy but probably sti= ll sufficient for low-stakes usage.

James


On Sat, Jul 9, 202= 2 at 10:31 PM Zac Greenwood <zachgr= w@gmail.com> wrote:
Sorting a seed alphabetically reduces entropy = by ~29 bits.

A 12-word s= eed has (12, 12) permutations or 479 million, which is ln(469m) / ln(2) ~= =3D 29 bits of entropy. Sorting removes this entropy entirely, reducing the= seed entropy from 128 to 99 bits.

Zac


On Fri, = 8 Jul 2022 at 16:09, James MacWhyte via bitcoin-dev <bitcoin-dev@lists.l= inuxfoundation.org> wrote:

What do you do if the "first" word (of 12), happens to be = the last word in the list alphabetically?

=
That couldn't happen. If one word is the very last from the wordli= st, it would end up at the end of your mnemonic=C2=A0once you rearrange you= r 12 words alphabetically.

However!=C2=A0

(@vjudeu) Ch= oosing 11 random words and then sorting them alphabetically before assignin= g=C2=A0a checksum would reduce entropy considerably. If you think about it,= to bruteforce the entire keyspace one would only need to come up with ever= y possible combination of 11 words=C2=A0+ 1 checksum. I'm not the best = at napkin math, but I think that leaves you with around=C2=A010 trillion co= mbinations, which would only take a couple months to exhaust with hardware = that can do 1 million guesses per second.


James
<= /div>
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000503cb105e366bef7--