[Haskell-cafe] 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[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  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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Ertugrul Söylemez]

Thomas DuBuisson  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?



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/


signature.asc
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Thomas DuBuisson]

On Thu, May 3, 2012 at 5:26 PM, Ertugrul Söylemez  wrote:
> Thomas DuBuisson  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?
>
>    
>
> 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
> Haskell-Cafe@haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>

___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Ertugrul Söylemez]

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.
> 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 "
FPrint: BD28 3E3F BE63 BADD 4157  9134 D56A 37FA E5DD 8D11
Keysrv: hkp://subkeys.pgp.net/


signature.asc
Description: PGP signature
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Thomas DuBuisson]

On May 3, 2012 5:49 PM, "Ertugrul Söylemez"  wrote:

> 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.
> > 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Vincent Hanquez]

On 05/04/2012 04:56 AM, Thomas DuBuisson wrote:
On May 3, 2012 5:49 PM, "Ertugrul Söylemez" mailto:e...@ertes.de>> 
wrote:


Thomas DuBuisson mailto:thomas.dubuis...@gmail.com>> 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Thomas DuBuisson]

Vincent uses gcc header files to get the AES instructions:

Header files of:

#include 
#include 

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  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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Brandon Allbery]

On Fri, May 4, 2012 at 10:11 AM, Vincent Hanquez  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  allber...@gmail.com
wandering unix systems administrator (available) (412) 475-9364 vm/sms
___
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[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
 #include

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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe

Re: [Haskell-cafe] Annoyed at System.Random

[Vincent Hanquez]

On 05/04/2012 03:18 PM, Brandon Allbery wrote:
On Fri, May 4, 2012 at 10:11 AM, Vincent Hanquez > 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
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe