Annoyed at System.Random

[Thomas DuBuisson]

Ryan,
I've grown annoyed at System.Random enough (specifically, StdGen).
How much, if any, pushback would there be if I put together a FFI
binding to a C AES-CTR based RNG.  There are many advantages:

0) The API wouldn't have to change (though some parts should, and some
change is already planned)
1) It can be fast (maybe not MT fast, but really quite good)
2) It's secure and the splitting properties can be related to
cryptographic problems.
3) It could use Intel NI instructions when available.
4) It's NIST standardized, so there exist known answer tests.
5) We could expose a method to fill an arbitrary buffer :: Storable a
=> Ptr a -> Int -> IO ()
6) The rest of the community doesn't have to do any of the work.

I'd be tempted to pull in the 'entropy' package for seeding, but will
make that a separate proposal.

Cheers,
Thomas

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ryan Newton]

Hi Thomas,

Personally, I would love to see that happen.  It seems like the best way to make split acceptable.

Is Brian Gladman's C implementation still best in class?  In my tests even without AESNI it could exceed the traditional System.Random in performance (https://github.com/rrnewton/intel-aes/wiki), while providing much better randomness and splitability.

Re: AESNI, my attempt at using the Intel provided asm for this introduced build fragility.  What would be the more portable way to do it?  Rewrite it using GCC intrinsics?  

   http://tab.snarc.org/posts/technical/2012-04-12-aes-intrinsics.html

  -Ryan

On Thu, May 3, 2012 at 7:43 PM, Thomas DuBuisson <[hidden email]> wrote:

Ryan,
I've grown annoyed at System.Random enough (specifically, StdGen).
How much, if any, pushback would there be if I put together a FFI
binding to a C AES-CTR based RNG.  There are many advantages:

0) The API wouldn't have to change (though some parts should, and some
change is already planned)
1) It can be fast (maybe not MT fast, but really quite good)
2) It's secure and the splitting properties can be related to
cryptographic problems.
3) It could use Intel NI instructions when available.
4) It's NIST standardized, so there exist known answer tests.
5) We could expose a method to fill an arbitrary buffer :: Storable a
=> Ptr a -> Int -> IO ()
6) The rest of the community doesn't have to do any of the work.

I'd be tempted to pull in the 'entropy' package for seeding, but will
make that a separate proposal.

Cheers,
Thomas

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ertugrul Söylemez]

Thomas DuBuisson <[hidden email]> wrote:

> I've grown annoyed at System.Random enough (specifically, StdGen).
> How much, if any, pushback would there be if I put together a FFI
> binding to a C AES-CTR based RNG.  There are many advantages:
>
> [...]
>
> I'd be tempted to pull in the 'entropy' package for seeding, but will
> make that a separate proposal.

Why reinvent the wheel?

    <http://hackage.haskell.org/package/cprng-aes>

Has both a System.Random and a Crypto-API interface.  As such it is
already connected to the 'entropy' package.


Greets,
Ertugrul

--
nightmare = unsafePerformIO (getWrongWife >>= sex)
http://ertes.de/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Thomas DuBuisson]

On Thu, May 3, 2012 at 5:26 PM, Ertugrul Söylemez <[hidden email]> wrote:

> Thomas DuBuisson <[hidden email]> wrote:
>
>> I've grown annoyed at System.Random enough (specifically, StdGen).
>> How much, if any, pushback would there be if I put together a FFI
>> binding to a C AES-CTR based RNG.  There are many advantages:
>>
>> [...]
>>
>> I'd be tempted to pull in the 'entropy' package for seeding, but will
>> make that a separate proposal.
>
> Why reinvent the wheel?
>
>    <http://hackage.haskell.org/package/cprng-aes>
>
> Has both a System.Random and a Crypto-API interface.  As such it is
> already connected to the 'entropy' package.

Vincent has done great work for Haskell+Crypto so I think he knows I
mean nothing personal when I say cprng-aes has the right idea done the
wrong way.  Why a new effort vs Vincent's package?

1. cprng-aes is painfully slow.
2. It doesn't use NI instructions (or any C implementation, currently).
3. It isn't backtracking resistent.  I plan to follow the SP and test
against the KATs.
4. Lots of people still use "random" by default, so it would be good
to have StdGen be something reasonable, where "reasonable" is from as
many perspectives as we can manage.

This isn't to say that we could use much of the structure and
higher-level code that Vincent has already done.

Cheers,
Thomas

>
>
> Greets,
> Ertugrul
>
> --
> nightmare = unsafePerformIO (getWrongWife >>= sex)
> http://ertes.de/
>
> _______________________________________________
> Haskell-Cafe mailing list
> [hidden email]
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ertugrul Söylemez]

Thomas DuBuisson <[hidden email]> wrote:

> Vincent has done great work for Haskell+Crypto so I think he knows I
> mean nothing personal when I say cprng-aes has the right idea done the
> wrong way.  Why a new effort vs Vincent's package?
>
> 1. cprng-aes is painfully slow.
> 2. It doesn't use NI instructions (or any C implementation,
> currently).
> 3. It isn't backtracking resistent.  I plan to follow the SP and test
> against the KATs.

I can't really tell whether the first two points are true.  If they are,
they should be really easy to fix and don't really require a new package
possibly with yet another interface.  The great thing about cprng-aes is
its simplicity.  It fulfills the design requirements for an opaque,
secure cryptographic library.  When you use the Crypto-API interface
it's really difficult to use the generator incorrectly.

About the third point:  This should be easy to fix and would probably be
the only breaking change (in that it would generate different sequences
than before).  However, it is questionable whether you want AES at all
in this case.  A hash function-based PRNG would probably be better.
This could indeed justify a new library.  On the other hand you want NI
instructions.

In any case I would contact Vincent about all this.  It would be great
if those changes could be incorporated transparently.


> 4. Lots of people still use "random" by default, so it would be good
> to have StdGen be something reasonable, where "reasonable" is from as
> many perspectives as we can manage.

Of course this is not cprng-aes' fault, so this point is one of its own
unrelated to my original response.  StdGen is really unfortunate and
should be replaced, but by what?  In an older thread this question
turned out to be difficult to answer.  An AES-based PRNG would probably
be a good compromise, but that is only my opinion.


Greets,
Ertugrul

--
Key-ID: E5DD8D11 "Ertugrul Soeylemez <[hidden email]>"
FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Thomas DuBuisson]

On May 3, 2012 5:49 PM, "Ertugrul Söylemez" <[hidden email]> wrote:

Thomas DuBuisson <[hidden email]> wrote:

> Vincent has done great work for Haskell+Crypto so I think he knows I
> mean nothing personal when I say cprng-aes has the right idea done the
> wrong way.  Why a new effort vs Vincent's package?
>
> 1. cprng-aes is painfully slow.
> 2. It doesn't use NI instructions (or any C implementation,
> currently).
> 3. It isn't backtracking resistent.  I plan to follow the SP and test
> against the KATs.

I can't really tell whether the first two points are true.

Feel free to investigate it yourself, I've convinced myself.  Vincent has added NI work to cryptocipher recently, but it still needs some corners smoothed.  I've contacted him about some of those already.  In the end I might use his C/ASM code for this task, but it is still lacking the ability to check for the NI instruction.

 

 If they are,
they should be really easy to fix and don't really require a new package

'random' isn't a new package.  We can't simply rename any package depending on crypto-api and add a new face because we should also consider the build deps.

About the third point:  This should be easy to fix and would probably be
the only breaking change (in that it would generate different sequences
than before).  However, it is questionable whether you want AES at all
in this case.  A hash function-based PRNG would probably be better.
This could indeed justify a new library.  On the other hand you want NI
instructions.

There are many ways to make a CTR based DRBG backtrack resistant.  As I've alluded to already - I'd just go with the NIST SP.

 

> 4. Lots of people still use "random" by default, so it would be good
> to have StdGen be something reasonable, where "reasonable" is from as
> many perspectives as we can manage.

Of course this is not cprng-aes' fault, so this point is one of its own
unrelated to my original response.

This is the core of the proposal, ignoring this is to ignore the purpose of the entire thread.

 

 StdGen is really unfortunate and
should be replaced, but by what?  In an older thread this question
turned out to be difficult to answer.

It was difficult back then because there was some confusion about adhering to the Haskell Report.  Well, Random isn't part of Haskell 2010+ and older standards include a copy in their own package, so we (read: Ryan) have a much freer hand.

Cheers,

Thomas

P.S. The email seems pointed, but I'm just merrily making points.

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Vincent Hanquez]

On 05/04/2012 01:35 AM, Thomas DuBuisson wrote:
> Vincent has done great work for Haskell+Crypto so I think he knows I
> mean nothing personal when I say cprng-aes has the right idea done the
> wrong way.  Why a new effort vs Vincent's package?
>
> 1. cprng-aes is painfully slow.
when using the haskell AES implementation yes. with AESNI it fly, and even more when
i'll have time to chunk the generation to bigger blocks (says 128 AES block at a
time)
> 2. It doesn't use NI instructions (or any C implementation, currently).
The NI instructions support are coming. and there's ton of already existing C
implementation
that could just be added.

> 3. It isn't backtracking resistent.  I plan to follow the SP and test
> against the KATs.
I'm not sure i understand this. what's backtracking resistent ?

--
Vincent

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Vincent Hanquez]

On 05/04/2012 04:56 AM, Thomas DuBuisson wrote:

> On May 3, 2012 5:49 PM, "Ertugrul Söylemez" <[hidden email] <mailto:[hidden email]>>
> wrote:
>
>     Thomas DuBuisson <[hidden email]
>     <mailto:[hidden email]>> wrote:
>
>     I can't really tell whether the first two points are true.
>
>
> Feel free to investigate it yourself, I've convinced myself.  Vincent has
> added NI work to cryptocipher recently, but it still needs some corners
> smoothed.  I've contacted him about some of those already.  In the end I might
> use his C/ASM code for this task, but it is still lacking the ability to check
> for the NI instruction.

My end goal is to have the user use transparently the fastest implementation
available to their architecture/cpu providing they use the high level module.
I've uploaded the cpu package which allows me to detect at runtime the aes
instruction (and the architecture), but i've been distracted in implementing
fast galois field arithmetics for GCM and XTS mode (with AES).

So any contributions going in this direction is more than welcome.

--
Vincent

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ryan Newton]

1. cprng-aes is painfully slow.

when using the haskell AES implementation yes. with AESNI it fly, and even more when
i'll have time to chunk the generation to bigger blocks (says 128 AES block at a time)

One data-point -- in "intel-aes" I needed to do bigger blocks to get decent performance.

 

2. It doesn't use NI instructions (or any C implementation, currently).

The NI instructions support are coming. and there's ton of already existing C implementation
that could just be added.

Oh, neat.  Could you share a pointer to some C code (with GCC aes intrinsics?) that can replace what the ASM does in the "intel-aes" package?

 

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Ryan Newton]

My end goal is to have the user use transparently the fastest implementation available to their architecture/cpu providing they use the high level module. I've uploaded the cpu package which allows me to detect at runtime the aes instruction (and the architecture), but i've been distracted in implementing fast galois field arithmetics for GCM and XTS mode (with AES).

Yes!  A worthy goal!

I think the proposal here is that we do the build/integration work to get something good which is portable enough and install-reliable enough to replace 'random'.  Then people who don't care will be using a good implementation by default.

That was my goal when I had my own small shot at this, but what I came up with was *very* build-fragile.  (Depended on assembler being available, or on prebuilt binaries being included for that package.)  You can see the Setup.hs customization I attempted to do in intel-aes to compensate, but it's not enough.

Can we write a cabal-compatible, really robust installer that will test the users system and always fall back rather than failing?

  -Ryan

P.S. How are you doing the CPUID test for NI instructions?  I used the *intel provided* test for this (in intel-aes) but I still had reports of incorrect identification on certain AMD CPUs...

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Thomas DuBuisson]

Vincent uses gcc header files to get the AES instructions:

Header files of:

    #include <wmmintrin.h>
    #include <tmmintrin.h>

And later calls of:

     x = _mm_aesenc_si128(m, K1);

But currently you must know you have AESNI and use a flag:

    cabal install cryptocipher -faesni

But if you are wrong:

    Illegal instruction (core dumped)


This is a great place to be - now we just take the CPU checking from
intel-aes, make a switch between Vincent's C and Gladman (in haskell
or out, I doesn't matter to me), graft on Ctr mode as specified then
it's all about matching the current 'random' API.

Cheers,
Thomas

On Fri, May 4, 2012 at 6:37 AM, Ryan Newton <[hidden email]> wrote:

>> My end goal is to have the user use transparently the fastest
>> implementation available to their architecture/cpu providing they use the
>> high level module. I've uploaded the cpu package which allows me to detect
>> at runtime the aes instruction (and the architecture), but i've been
>> distracted in implementing fast galois field arithmetics for GCM and XTS
>> mode (with AES).
>
>
> Yes!  A worthy goal!
>
> I think the proposal here is that we do the build/integration work to get
> something good which is portable enough and install-reliable enough to
> replace 'random'.  Then people who don't care will be using a good
> implementation by default.
>
> That was my goal when I had my own small shot at this, but what I came up
> with was *very* build-fragile.  (Depended on assembler being available, or
> on prebuilt binaries being included for that package.)  You can see the
> Setup.hs customization I attempted to do in intel-aes to compensate, but
> it's not enough.
>
> Can we write a cabal-compatible, really robust installer that will test the
> users system and always fall back rather than failing?
>
>   -Ryan
>
> P.S. How are you doing the CPUID test for NI instructions?  I used the
> *intel provided* test for this (in intel-aes) but I still had reports of
> incorrect identification on certain AMD CPUs...
>

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Vincent Hanquez]

On 05/04/2012 02:37 PM, Ryan Newton wrote:

>
>     My end goal is to have the user use transparently the fastest
>     implementation available to their architecture/cpu providing they use the
>     high level module. I've uploaded the cpu package which allows me to detect
>     at runtime the aes instruction (and the architecture), but i've been
>     distracted in implementing fast galois field arithmetics for GCM and XTS
>     mode (with AES).
>
>
> Yes!  A worthy goal!
>
> I think the proposal here is that we do the build/integration work to get
> something good which is portable enough and install-reliable enough to replace
> 'random'.  Then people who don't care will be using a good implementation by
> default.
>
> That was my goal when I had my own small shot at this, but what I came up with
> was *very* build-fragile.  (Depended on assembler being available, or on
> prebuilt binaries being included for that package.)  You can see the Setup.hs
> customization I attempted to do in intel-aes to compensate, but it's not enough.
>
> Can we write a cabal-compatible, really robust installer that will test the
> users system and always fall back rather than failing?

That was my original plan, until i find out that it's not really possible.

For the language, i think assembly is a no-no with cabal, as such it need to be
embedded in gcc inline assembly if you want to have something that works (unless
there's a secret way to run assembler in a portable fashion in cabal).

Which is the reason behind why i settled on intrinsics, as i didn't have to do
the assembly directly. It appears more portable as well
as every major compiler seems to support it (with difference of course, it would
too simple otherwise (!))

> P.S. How are you doing the CPUID test for NI instructions?  I used the *intel
> provided* test for this (in intel-aes) but I still had reports of incorrect
> identification on certain AMD CPUs...
>

I haven't done it yet, but it should be just a matter of this piece of code for
Intel and AMD:

import System.Cpuid
import Data.Bits

supportAESNI :: IO Bool
supportAESNI = cpuid 1 >>= \(_,_,ecx,_) -> ecx `testBit` 25

--
Vincent

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Brandon Allbery]

On Fri, May 4, 2012 at 10:11 AM, Vincent Hanquez <[hidden email]> wrote:

For the language, i think assembly is a no-no with cabal, as such it need to be embedded in gcc inline assembly if you want to have something that works (unless there's a secret way to run assembler in a portable fashion in cabal).

I don't know if cabal knows this, but assembler files with .s (and maybe .asm on Windows?) extension are recognized by most C compilers and handed off to the assembler; as such, simply augmenting cabal's C rules with those extensions should be sufficient.

--
brandon s allbery                                      [hidden email]
wandering unix systems administrator (available)     [phone] vm/sms

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Vincent Hanquez]

On 05/04/2012 02:33 PM, Ryan Newton wrote:

>
>         1. cprng-aes is painfully slow.
>
>     when using the haskell AES implementation yes. with AESNI it fly, and even
>     more when
>     i'll have time to chunk the generation to bigger blocks (says 128 AES
>     block at a time)
>
>
> One data-point -- in "intel-aes" I needed to do bigger blocks to get decent
> performance.

Yes, it's a slightly random value here, although it's a tradeoff with memory
usage and
performance, 128 blocks would do quite well compared to any haskell
implementation that goes 1 block at a time [1]

[1] because you'll have to drop in/out of C, and reload the SSE registers each time.

>         2. It doesn't use NI instructions (or any C implementation, currently).
>
>     The NI instructions support are coming. and there's ton of already
>     existing C implementation
>     that could just be added.
>
>
> Oh, neat.  Could you share a pointer to some C code (with GCC aes intrinsics?)
> that can replace what the ASM does in the "intel-aes" package?
Just have a look in cryptocipher with cbits/aes/x86ni.c

--
Vincent

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Vincent Hanquez]

On 05/04/2012 03:05 PM, Thomas DuBuisson wrote:

> Vincent uses gcc header files to get the AES instructions:
>
> Header files of:
>
>      #include<wmmintrin.h>
>      #include<tmmintrin.h>
>
> And later calls of:
>
>       x = _mm_aesenc_si128(m, K1);
>
> But currently you must know you have AESNI and use a flag:
>
>      cabal install cryptocipher -faesni
>
> But if you are wrong:
>
>      Illegal instruction (core dumped)

Of course that's expected as of now, since it's not finished and i had to push a
new release (related to some significant performance improvement for
RSA/DH/DSA), the code is there as a "technology preview".

But the goal is to turn unconditionally the AESNI "flag" when arch is x86 or
x86_64, which in this case the implementation would rely on the runtime cpuid
check to use the aesni fastpath or not.

>
> This is a great place to be - now we just take the CPU checking from
> intel-aes, make a switch between Vincent's C and Gladman (in haskell
> or out, I doesn't matter to me), graft on Ctr mode as specified then
> it's all about matching the current 'random' API.
Please don't take the intel-aes test implementation. it's skewed to just support
Intel,
since it basically testing for the cpu string "GenuineIntel".

The only necessary test is the cpuid 1 with ecx having the 25th bit set.
It should just work providing cpus other than intel have matching cpuid 1 layout
(which as far i'm concerned seems to be the case in most cases)

--
Vincent

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe

[Vincent Hanquez]

On 05/04/2012 03:18 PM, Brandon Allbery wrote:

> On Fri, May 4, 2012 at 10:11 AM, Vincent Hanquez <[hidden email]
> <mailto:[hidden email]>> wrote:
>
>     For the language, i think assembly is a no-no with cabal, as such it need
>     to be embedded in gcc inline assembly if you want to have something that
>     works (unless there's a secret way to run assembler in a portable fashion
>     in cabal).
>
>
> I don't know if cabal knows this, but assembler files with .s (and maybe .asm
> on Windows?) extension are recognized by most C compilers and handed off to
> the assembler; as such, simply augmenting cabal's C rules with those
> extensions should be sufficient.

That might works, although you might end up with some corner case portability
issues.
Wrapping them in C should be more practical and you could write something like
this for maximum portability (compiler,systems,..):

#if system_that_works_with_inline_asm
asm inline("instr1; instr2;", ....);
#else
  /* fallback to C */
#endif

--
Vincent

_______________________________________________
Haskell-Cafe mailing list
[hidden email]
http://www.haskell.org/mailman/listinfo/haskell-cafe