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