Subject: [saag] CFRG Presentation on Algebraic Eraser

From: "Derek Atkins" <[email-masked]>
Date: Tue, 24 Mar 2015 23:53:11 -0400

Hi,

On Wednesday in CFRG my colleague and I are presenting the Algebraic
Eraser, a public key crypto system targeted at embedded, low-resource, IoT
systems that performs 70-200x better than ECC in time and power
consumption.  If you're at all interested in seeing viable, performant
public key crypto on extremely constrained devices I encourage you to
attend CFRG at 1pm on Wednesday.

The abstract of the talk:

The Algebraic Eraser (AE), introduced by Anshel, Anshel, Goldfeld, and
Lemieux in 2006, is a key agreement protocol for public-key cryptography
which was designed to be suitable for implementation on low-cost platforms
with constrained computational resources, such as RFID, NFC, and other
platforms associated with the "Internet of Things."  One novel feature of
the protocol is that its complexityscales linearly with the desired
security, unlike other asymmetric methods such as RSA and ECC.  In this
talk we give an overview of the protocol and present recent hardware
timing data comparing the performance of AE with ECC.

-derek

-- 
       Derek Atkins                 617-623-3745
       [email-masked]             www.ihtfp.com
       Computer and Internet Security Consultant

---

From: Ben Laurie <[email-masked]>
Date: Wed, 25 Mar 2015 13:22:33 +0000

> timing data comparing the performance of AE with ECC.

Has there been any analysis of AE?

---

From: Yoav Nir <[email-masked]>
Date: Wed, 25 Mar 2015 08:44:28 -0500

Hi, Derek

If it indeed "performs 70-200x better than ECC in time and power consumption”, why is it appropriate only for IoT systems?  Why is it inappropriate for quad-core 3 GHz 16 GB desktop systems connecting to 32-core 3GHz 128GB servers?

Yoav

> On Mar 24, 2015, at 10:53 PM, Derek Atkins <[email-masked]> wrote:
> 
> Hi,
> 
> _______________________________________________
> saag mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/saag

---

From: Watson Ladd <[email-masked]>
Date: Wed, 25 Mar 2015 07:17:49 -0700

> timing data comparing the performance of AE with ECC.

This protocol appears to be based on conjugation in the braid group,
with some variations. I've seen http://arxiv.org/pdf/0801.4786v1.pdf
attacking this proposal. Are there other analyses we should be looking
at?

Sincerely,
Watson Ladd

-- 
"Those who would give up Essential Liberty to purchase a little
Temporary Safety deserve neither  Liberty nor Safety."
-- Benjamin Franklin

---

From: "Derek Atkins" <[email-masked]>
Date: Wed, 25 Mar 2015 10:37:06 -0400

Hi,

> attacking this proposal. Are there other analyses we should be looking

Sure.  You can look at http://arxiv.org/pdf/1202.0598v1.pdf and
http://arxiv.org/pdf/1105.1141v1.pdf which talk to the two proposed
attacks and show how they don't actually work.

Thanks,

-derek

---

From: "Derek Atkins" <[email-masked]>
Date: Wed, 25 Mar 2015 10:41:59 -0400

Hi Ben,

> Has there been any analysis of AE?

Yes, there has.  Over the last decade since AE was first proposed there
have been only two classes of attacks ever found, both of which have been
refuted (see my previous reply to Watson Ladd).  In short, there was a
class of weak keys if you randomly generate your private keys (but RSA has
the same issue, you cannot chose a "random N", you need it to be the
product of two large primes).  The other attack basically boils down to
having keys that are too short are easy to break.  Details are in my other
reply.

Thanks for your interest,

-derek

---

From: "Derek Atkins" <[email-masked]>
Date: Wed, 25 Mar 2015 10:50:14 -0400

Hi Yoav,

On Wed, March 25, 2015 9:44 am, Yoav Nir wrote:
> Hi, Derek
>
> If it indeed "performs 70-200x better than ECC in time and power
> consumption”, why is it appropriate only for IoT systems?  Why is it
> inappropriate for quad-core 3 GHz 16 GB desktop systems connecting to
> 32-core 3GHz 128GB servers?

Thank you for your interest.  I'll point out that I never said it was
"inappropriate for quad-core 3GHz 16 GB desktop systems connecting to
32-core 3GHz 128GB servers".  Indeed, I never said anything about the
appropriateness or inappropriateness of AE for a particular use case.  I
just said that we're focused on IoT because that's a place that is
currently not being served by existing Public Key Cryptography methods due
to the extremely constrained environments and computational complexity of
existing PK methods.

Thanks,

-derek

---

From: Viktor Dukhovni <[email-masked]>
Date: Wed, 25 Mar 2015 15:15:10 +0000

> timing data comparing the performance of AE with ECC.

The description of CBKAP on page 11 in the paper:

    http://www.securerf.com/wp-content/uploads/2014/03/SecureRF-Technical-White-Paper-06-with-Appendix-A-B.pdf

appears to rely on a TTP (think KDC?) that creates the commuting
generator sets, and is able to impersonate all the users of the
protocol (with the chosen parameters).

Is this why the system is for IoT, rather than broad use on the
public Internet.

-- 
	Viktor.

---

From: Rene Struik <[email-masked]>
Date: Wed, 25 Mar 2015 11:52:19 -0400

Dear Derek:

The email below contains some pointers to public-key crypto in standards and products, including those in the IoT space (whatever that term in its currently diluted form means). So, there is some evidence that widely accepted public key crypto fits in at least part of that application domain.

Are there any "Algebraic Eraser challenges", with price money $10k or up, similar to the Certicom ECC challenges around 2000? That might help in enticing research interest.

I am looking forward to your presentation.

Best regards, Rene

==
[excerpt of your email of Wed March 25, 2015, 10.50am EDT]
"I just said that we're focused on IoT because that's a place that is currently not being served by existing Public Key Cryptography methods due
to the extremely constrained environments and computational complexity of existing PK methods."

-------- Forwarded Message --------
Subject: 	some pointers to public-key crypto in standards and products
Date: 	Wed, 11 Mar 2015 09:45:29 -0400
From: 	Rene Struik <[email-masked]>
To: 	[email-masked] <[email-masked]>, tisch-security 
<[email-masked]>

Dear Pascal:

As requested, please find below some pointers to cryptographic support
for public key operations in industry specifications and products.

Some standards and specifications that include public key support:
ZigBee IP, ISA SP100, ICAO ePassport, EMVCo chipcards, Connected
vehicles (IEEE 1609.2, etc.), IEEE 802.11/Wifi Alliance, PIV access
control card (FIPS 201, etc.), CoRE/Coap

Some chipsets:
http://www.atmel.com/Images/Atmel-8923S-CryptoAuth-ATECC508A-Datasheet-Summary.pdf
http://www.ti.com/lit/ds/symlink/cc2538.pdf

Reference to any external standard or any external product does not
indicate endorsement hereof or vouching for security claims.

There are thousands of academic papers on implementation of symmetric
and public key crypto on small devices, including hundreds on more
exotic - to mainstream audience - techniques on squeezing crypto on
smaller and smaller devices (so-called light-weight cryptography). For
those interested in a US DARPA initiative to create a complete
anti-cloning solution (including crypto, antenna, packaging) for a
penny, see http://www.darpa.mil/NewsEvents/Releases/2014/02/24.aspx.

Some of these aspects were discussed on the 6TiSCH security calls, most
recently on the Feb 24, 2015 call:
http://www.ietf.org/mail-archive/web/6tisch-security/current/msg00489.html

I hope this helps. It should at least provide some evidence that
cryptographic components are fast reaching commodity status.

Final note: of course, there is still plenty of room to use crypto
unwisely/imprudently. That is why people like me do not have to be idle.

Best regards, Rene

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363

-- 
email: [email-masked] | Skype: rstruik
cell: +1 (647) 867-5658 | US: +1 (415) 690-7363