Re: [Cfrg] (on Algebraic Eraser) Re: Meeting notes
"Derek Atkins" <derek@ihtfp.com> Mon, 30 March 2015 14:15 UTC
Return-Path: <derek@ihtfp.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DB4AC1ACF5D for <cfrg@ietfa.amsl.com>; Mon, 30 Mar 2015 07:15:32 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.9
X-Spam-Level:
X-Spam-Status: No, score=-1.9 tagged_above=-999 required=5 tests=[BAYES_00=-1.9] autolearn=ham
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8F49Z4zSMp6P for <cfrg@ietfa.amsl.com>; Mon, 30 Mar 2015 07:15:30 -0700 (PDT)
Received: from mail2.ihtfp.org (mail2.ihtfp.org [IPv6:2001:4830:143:1::3a11]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 2E9471ACEE9 for <cfrg@irtf.org>; Mon, 30 Mar 2015 07:15:30 -0700 (PDT)
Received: from localhost (localhost [127.0.0.1]) by mail2.ihtfp.org (Postfix) with ESMTP id 7A9D5E2034; Mon, 30 Mar 2015 10:15:27 -0400 (EDT)
Received: from mail2.ihtfp.org ([127.0.0.1]) by localhost (mail2.ihtfp.org [127.0.0.1]) (amavisd-maia, port 10024) with ESMTP id 05143-08; Mon, 30 Mar 2015 10:15:25 -0400 (EDT)
Received: by mail2.ihtfp.org (Postfix, from userid 48) id ED684E2045; Mon, 30 Mar 2015 10:15:24 -0400 (EDT)
Received: from 192.168.248.204 (SquirrelMail authenticated user warlord) by mail2.ihtfp.org with HTTP; Mon, 30 Mar 2015 10:15:24 -0400
Message-ID: <03a62f9e7e4e83a7353461676b96948c.squirrel@mail2.ihtfp.org>
In-Reply-To: <55194E56.3030509@gmail.com>
References: <CAHOTMVKUyNsA7ux4epk8LwR0w0Eh7dh0G3xTXB3O9m8jQPS3EQ@mail.gmail.com> <0C65868C-1725-4B32-A562-62C9DF36A956@gmail.com> <c65696d44c65b12478532bcb01fb2ef3.squirrel@mail2.ihtfp.org> <94D99ECB-98CA-4D25-897D-BA4BA8178409@gmail.com> <87y4mhtf5a.fsf@alice.fifthhorseman.net> <F7CF0AB9-4F3E-4FD4-B4D2-2F5172CB4BF2@gmail.com> <20150330104505.GA11195@LK-Perkele-VII> <55194E56.3030509@gmail.com>
Date: Mon, 30 Mar 2015 10:15:24 -0400
From: Derek Atkins <derek@ihtfp.com>
To: Rene Struik <rstruik.ext@gmail.com>
User-Agent: SquirrelMail/1.4.22-14.fc20
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"
Content-Transfer-Encoding: 8bit
X-Priority: 3 (Normal)
Importance: Normal
X-Virus-Scanned: Maia Mailguard 1.0.2a
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/8z9bpC5MdimhsquM_HI32pm3efw>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
Subject: Re: [Cfrg] (on Algebraic Eraser) Re: Meeting notes
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 30 Mar 2015 14:15:33 -0000
Thank you Rene, In the example we gave in the presentation we are using B16F256 to reach a security level of 2^128. That's a 16x16 matrix over the field 256 (2^8). -derek On Mon, March 30, 2015 9:23 am, Rene Struik wrote: > Dear colleagues: > > From the emails on Algebraic Eraser I have seen on this list, it seems > clear that most have not given this algorithm any technical look. What > about actually doing this, instead of having email completely tangential > email exchanges about a "black box" one did not care to open? > > Speculation on implementation security, sizes of primes involved, key > generation protocols, etc., seem somewhat premature if one did not first > look at and tried to understand the algorithm itself... > > Ilari: the Algebraic Eraser paper of 2006 [1] includes some example > instantiations with sparse 14 x 14 matrices over GF(p), with p=13. No > clue at all where your p=2^31-1 comes from. > > Rene > > [1] Algebraic Eraser - Technical White Paper (Iris Anshel, Michael > Anshel, Dorian Goldfeld, Stephane Lemieux, Contemporary Mathematics, 2006) > > On 3/30/2015 6:45 AM, Ilari Liusvaara wrote: >> On Mon, Mar 30, 2015 at 01:26:38PM +0300, Yoav Nir wrote: >>>> On Mar 28, 2015, at 4:39 PM, Daniel Kahn Gillmor >>>> <dkg@fifthhorseman.net> wrote: >>>> >>>> On Fri 2015-03-27 09:44:14 -0500, Yoav Nir wrote: >>>>> Is that the same for AE? Because if it is, you could just generate >>>>> those parameters, stick them in the draft and be done with it (up to >>>>> some NUMS claims that can be solved with a key generation ceremony >>>>> that need happen only once. >>>> I think this key generation ceremony is the part that people were >>>> expressing concern about in the meeting. >>>> >>>> It's not clear that we have a clear story about how to do this in a >>>> reliable, future-proof way (that is, so that arbitrary people in the >>>> future can easily refute any speculation that the original generation >>>> procedure was somehow backdoored). >>>> >>>> Many of us on this list can probably propose clever "performance art" >>>> events that seem like they'd be likely to satisfy this property today >>>> for most of us. But if we aim for some set of parameters that will >>>> still be used a generation from now, that seems harder to predict. >>> I’m not a big fan of performance art, but if the claims of 50x >>> performance gain are true, I think a lot of us will be willing >>> to just through a lot of hoops to get it. And I mean for all >>> the Internet, not just SmartObjects. >> I haven't really looked, but on surface the algorithm doesn't look to >> be friendly for constant-time implementation. Matrix row or column >> swaps are involved? >> >> So constant-time implementation would likely be a lot slower (it could >> still be much faster than ECC). >> >> Modern CPUs and OSes are pretty ridiculously vulernable to timing >> attacks. Even across VMs. >> >> >> Another advantage: It uses medium primes, which are much >> easier to work with than large primes (one can't use medium primes >> with ECC due to weak fields). For CPU work, 2^31-1 looks to be pretty >> convinient prime. >> >> >> -Ilari >> >> _______________________________________________ >> Cfrg mailing list >> Cfrg@irtf.org >> http://www.irtf.org/mailman/listinfo/cfrg > > > -- > email: rstruik.ext@gmail.com | Skype: rstruik > cell: +1 (647) 867-5658 | US: +1 (415) 690-7363 > > _______________________________________________ > Cfrg mailing list > Cfrg@irtf.org > http://www.irtf.org/mailman/listinfo/cfrg > -- Derek Atkins 617-623-3745 derek@ihtfp.com www.ihtfp.com Computer and Internet Security Consultant
- [Cfrg] Meeting notes Tony Arcieri
- Re: [Cfrg] Meeting notes Yoav Nir
- Re: [Cfrg] Meeting notes Derek Atkins
- Re: [Cfrg] Meeting notes Yoav Nir
- Re: [Cfrg] Meeting notes Derek Atkins
- Re: [Cfrg] Meeting notes Watson Ladd
- Re: [Cfrg] Meeting notes Daniel Kahn Gillmor
- Re: [Cfrg] Meeting notes Johannes Merkle
- Re: [Cfrg] Meeting notes Yoav Nir
- Re: [Cfrg] Meeting notes Ilari Liusvaara
- [Cfrg] (on Algebraic Eraser) Re: Meeting notes Rene Struik
- Re: [Cfrg] (on Algebraic Eraser) Re: Meeting notes Derek Atkins
- Re: [Cfrg] (on Algebraic Eraser) Re: Meeting notes Nico Williams
- Re: [Cfrg] Meeting notes Nico Williams
- Re: [Cfrg] (on Algebraic Eraser) Re: Meeting notes Rene Struik
- Re: [Cfrg] (on Algebraic Eraser) Re: Meeting notes Nico Williams
- Re: [Cfrg] Meeting notes Derek Atkins
- Re: [Cfrg] Meeting notes Alexey Melnikov