Is ansi_cprng.c supposed to be an implmentation of X9.31?

Is ansi_cprng.c supposed to be an implmentation of X9.31?

[George Spelvin]

I've been trying to understand the crypto layer, and it's a bit of a
struggle because I'm trying to learn how it's supposed to work by
reading the code, and I keep finding code I want to fix.

ansi_cprng.c is the current itch I'm eager to scratch.

Other than enough implementation stupidities to make me scream
(particularly the "rand_data_valid" variable name which is actually a
count of INvalid data, and  keeping 5 blocks of state, including sensitive
previous output, when only 3 are needed), one thing I can't help noticing
is that this is definitely NOT conformant with the X9.17/X9.31 spec.

That's because the spec requires a timestamp for each output block
to provide additional entropy, and a counter won't cut it.

I'm fixing the obvious things, but on this point, I have two choices:

1. Add some comments clarifying that the "Based on" part of the header
   is anything but a claim of compliance; those specs are for an RNG,
   while this is a PRNG.  And probably delete all the FIPS stuff, as
   there's no spec to claim compliance with.  Or
2. Fix the code to use random_get_entropy() and jiffies for the
   DT seed vector.

In the latter case, I'd have to leave the current deterministic code as
an option for self-testing, but I'd drop the recommended seedsize
to DEFAULT_PRNG_KSZ + DEFAULT_BLK_SZ (one key and one IV), and have
an internal flag indicating whether to use an incrementing DT vector
or generate it fresh.

If some code (like the current self-test code) provides an extra
DEFAULT_BLK_SZ of seed material, it would go into determinsitic mode,
but if it's missing, DT would be generated dynamically.

But that's a question of design intent, and I can't intuit that from the
code.  Can someome enlighten me as to which option is preferred?

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[Neil Horman]

On Fri, Nov 28, 2014 at 06:23:51PM -0500, George Spelvin wrote:
> I've been trying to understand the crypto layer, and it's a bit of a
> struggle because I'm trying to learn how it's supposed to work by
> reading the code, and I keep finding code I want to fix.
> 
Patches welcome.

> ansi_cprng.c is the current itch I'm eager to scratch.
> 
> Other than enough implementation stupidities to make me scream
> (particularly the "rand_data_valid" variable name which is actually a
Its actually a counter of the number of valid random data bytes in the buffer
being returned to a caller, as well as an index into the internal buffer from
which to draw fresh random data.  Sorry if you don't get that, but it seems
pretty clear.

> count of INvalid data, and  keeping 5 blocks of state, including sensitive
> previous output, when only 3 are needed), one thing I can't help noticing
Not sure where you're getting that from, only 1 block of random data is stored
at any one time to return to a caller

> is that this is definitely NOT conformant with the X9.17/X9.31 spec.
> 
This is the document it was based of off:
http://csrc.nist.gov/groups/STM/cavp/documents/rng/931rngext.pdf

>From my read, it seems to be in complete compliance.

> That's because the spec requires a timestamp for each output block
> to provide additional entropy, and a counter won't cut it.
> 
The document places no constrints on the value or progression of DT.  As such a
counter is as valid as any other implementation.  You're welcome to enhance that
however, as I said, patches welcome.

> I'm fixing the obvious things, but on this point, I have two choices:
> 
> 1. Add some comments clarifying that the "Based on" part of the header
>    is anything but a claim of compliance; those specs are for an RNG,
>    while this is a PRNG. 
Please read more closely, the header clearly states this is a PRNG
implementation, and a quick google search of the terms in the header bring up
the document referenced above, with which this cprng is in compliance with.

>  And probably delete all the FIPS stuff, as
>    there's no spec to claim compliance with.  Or
Maybe do some research before making big claims like this:
http://csrc.nist.gov/publications/fips/fips140-2/fips1402annexc.pdf

Its just a draft, but digging through the NIST site will bring up the approved
version.  Both show that a 3 DES CPRNG based on ANSI X9.31 is valid, and
provides  a reference to the paper above as the implementation guideline.

> 2. Fix the code to use random_get_entropy() and jiffies for the
>    DT seed vector.
> 
Sure, knock yourself out.  I don't consider it more or less valid to do so, but
patches are welcome.

> In the latter case, I'd have to leave the current deterministic code as
> an option for self-testing, but I'd drop the recommended seedsize
> to DEFAULT_PRNG_KSZ + DEFAULT_BLK_SZ (one key and one IV), and have
> an internal flag indicating whether to use an incrementing DT vector
> or generate it fresh.
Yup.  Strictly speaking the API is in-kernel only, so you don't really have to
worry about handling backwards compatibility, but if you don't allow for DT to
be specified as an initial value, you won't be able to validate against any of
the test vectors that NIST provides:
http://csrc.nist.gov/groups/STM/cavp/documents/rng/RNGVS.pdf

I will also point out that CPRNG's are designed such that peers communicating
with a cprng are expected to be able to predect the cprng output, which implies
that the DT value needs to remain predictable as well.  Using an actual date
time vector is going to make communication like that very unstable if there is
even a little clock drift on either system.  As such, while its less entropy,
using a simple arbitrary vector with an increment on each random data generation
leads to greater stability and predictability for those with the key.  The data
provided in the validation test in Appendix B.1.5 of the above document supports
that, as the DT value is arbitrary and incremented by one on each iteration.

> 
> If some code (like the current self-test code) provides an extra
> DEFAULT_BLK_SZ of seed material, it would go into determinsitic mode,
> but if it's missing, DT would be generated dynamically.
> 
Sure, patches welcome.

> But that's a question of design intent, and I can't intuit that from the
> code.  Can someome enlighten me as to which option is preferred?
> 
Definately keep the ability to support external setting of DT, as you can't pass
any validation tests without it.

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[George Spelvin]

>> Other than enough implementation stupidities to make me scream
>> (particularly the "rand_data_valid" variable name which is actually a

> Its actually a counter of the number of valid random data bytes in the buffer
> being returned to a caller, as well as an index into the internal buffer from
> which to draw fresh random data.  Sorry if you don't get that, but it seems
> pretty clear.

As you can see, I ended up choosing less abrasive wording in the version I
*thought* was public; this got launched into the void while in draft form.
Sorry about that.

Oh, its use as an index into the read_data array is clear enough;
it's just that the fact that the number of valid bytes in that
array is DEFAULT_BLOCK_SZ - ctx->rand_data_valid seems "obviously
backward" to me.

You'd think "ctx->rand_data_valid = 0" would mean "no data is valid;
force update cycle next access", but nope...

> is that this is definitely NOT conformant with the X9.17/X9.31 spec.
 
> This is the document it was based of off:
> http://csrc.nist.gov/groups/STM/cavp/documents/rng/931rngext.pdf

Ah, I actually read that, but I didn't remember that the "Based on"
wording is a direct quote.

If you go to the original ANSI specs (which I've read in the past,
but din't have a web-accessible copy to link to), they're a bit
more explicit on the point.

> Please read more closely, the header clearly states this is a PRNG
> implementation, and a quick google search of the terms in the header bring up
> the document referenced above, with which this cprng is in compliance with.

Yes, it was quite clear that a strict reading of the comments said that
it was a PRNG, but I lost track of the fact that "Random Number Generator
Based on ANSI X9.31 Appendix A.2.4" was NIST's wording that was being
quoted, and was left with the impression that compliance to the ANSI spec
(which *does* call for a high resolution timestamp) was being implied.

I either wanted to provide the implied compliance or clarify the
absence of it.

> Sure, knock yourself out.  I don't consider it more or less valid to do so,
> but patches are welcome.

Coming right up!

> Definately keep the ability to support external setting of DT, as you
> can't pass any validation tests without it.

Yes, I've already figured that out when studying the impact of such a
change.  Since there's already special-case handling of with/without
a DT vector, that seemed the obvious thing to hook into.

The two changes that affected callers, which I didn't feel very confident
about my understanding of, were:
1. Changing the recommended seed size, and
2. Using actual random seed material.

The other one, which I have to think *very* hard about, is whether
using the same seed material as /dev/random in this much weaker
cryptographic construction will introduce a flaw in *it*.

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[Neil Horman]

On Sat, Nov 29, 2014 at 02:32:05PM -0500, George Spelvin wrote:
> >> Other than enough implementation stupidities to make me scream
> >> (particularly the "rand_data_valid" variable name which is actually a
> 
> > Its actually a counter of the number of valid random data bytes in the buffer
> > being returned to a caller, as well as an index into the internal buffer from
> > which to draw fresh random data.  Sorry if you don't get that, but it seems
> > pretty clear.
> 
> As you can see, I ended up choosing less abrasive wording in the version I
> *thought* was public; this got launched into the void while in draft form.
> Sorry about that.
> 
> Oh, its use as an index into the read_data array is clear enough;
> it's just that the fact that the number of valid bytes in that
> array is DEFAULT_BLOCK_SZ - ctx->rand_data_valid seems "obviously
> backward" to me.
> 
> You'd think "ctx->rand_data_valid = 0" would mean "no data is valid;
> force update cycle next access", but nope...
> 
> > is that this is definitely NOT conformant with the X9.17/X9.31 spec.
>  
> > This is the document it was based of off:
> > http://csrc.nist.gov/groups/STM/cavp/documents/rng/931rngext.pdf
> 
> Ah, I actually read that, but I didn't remember that the "Based on"
> wording is a direct quote.
> 
> If you go to the original ANSI specs (which I've read in the past,
> but din't have a web-accessible copy to link to), they're a bit
> more explicit on the point.
> 
> > Please read more closely, the header clearly states this is a PRNG
> > implementation, and a quick google search of the terms in the header bring up
> > the document referenced above, with which this cprng is in compliance with.
> 
> Yes, it was quite clear that a strict reading of the comments said that
> it was a PRNG, but I lost track of the fact that "Random Number Generator
> Based on ANSI X9.31 Appendix A.2.4" was NIST's wording that was being
> quoted, and was left with the impression that compliance to the ANSI spec
> (which *does* call for a high resolution timestamp) was being implied.
> 
> I either wanted to provide the implied compliance or clarify the
> absence of it.
> 
> > Sure, knock yourself out.  I don't consider it more or less valid to do so,
> > but patches are welcome.
> 
> Coming right up!
> 
> > Definately keep the ability to support external setting of DT, as you
> > can't pass any validation tests without it.
> 
> Yes, I've already figured that out when studying the impact of such a
> change.  Since there's already special-case handling of with/without
> a DT vector, that seemed the obvious thing to hook into.
> 
> The two changes that affected callers, which I didn't feel very confident
> about my understanding of, were:
> 1. Changing the recommended seed size, and
Well, you only need to worry about the users of the API in the kernel, for which
I think there is only one currently, so I would say change the seed size if you
want, and make sure the one caller matches it appropriately.  Not saying I agree
with the change (or disagree with it), but I think you don't really need to
worry about it.

> 2. Using actual random seed material.
> 
Thats really a call for the allocator of a cprng to make.  When you allocate a
cprng instance, you have to reset it before you use it, so you have to provide a
new IV, DT and KEY value anyway.  If the caller wants to provide real random
material, they are prefectly able to.  If you want you can default to using
random data when no seed is provided, but I wouldn't recommend it, since the
random pool can block, and we might be resetting the cprng in a non-blocking
context.  I would say just leave this to the caller.

> The other one, which I have to think *very* hard about, is whether
> using the same seed material as /dev/random in this much weaker
> cryptographic construction will introduce a flaw in *it*.
> 

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[Stephan Mueller]

Am Samstag, 29. November 2014, 14:32:05 schrieb George Spelvin:

Hi George,

>>> Other than enough implementation stupidities to make me scream
>>> (particularly the "rand_data_valid" variable name which is actually
>>> a
>> 
>> Its actually a counter of the number of valid random data bytes in
>> the buffer being returned to a caller, as well as an index into the
>> internal buffer from which to draw fresh random data.  Sorry if you
>> don't get that, but it seems pretty clear.
>
>As you can see, I ended up choosing less abrasive wording in the
>version I *thought* was public; this got launched into the void while
>in draft form. Sorry about that.
>
>Oh, its use as an index into the read_data array is clear enough;
>it's just that the fact that the number of valid bytes in that
>array is DEFAULT_BLOCK_SZ - ctx->rand_data_valid seems "obviously
>backward" to me.
>
>You'd think "ctx->rand_data_valid = 0" would mean "no data is valid;
>force update cycle next access", but nope...
>
>> is that this is definitely NOT conformant with the X9.17/X9.31 spec.
>> 
>> This is the document it was based of off:
>> http://csrc.nist.gov/groups/STM/cavp/documents/rng/931rngext.pdf
>
>Ah, I actually read that, but I didn't remember that the "Based on"
>wording is a direct quote.
>
>If you go to the original ANSI specs (which I've read in the past,
>but din't have a web-accessible copy to link to), they're a bit
>more explicit on the point.
>
>> Please read more closely, the header clearly states this is a PRNG
>> implementation, and a quick google search of the terms in the header
>> bring up the document referenced above, with which this cprng is in
>> compliance with.
>Yes, it was quite clear that a strict reading of the comments said that
>it was a PRNG, but I lost track of the fact that "Random Number
>Generator Based on ANSI X9.31 Appendix A.2.4" was NIST's wording that
>was being quoted, and was left with the impression that compliance to
>the ANSI spec (which *does* call for a high resolution timestamp) was
>being implied.
>
>I either wanted to provide the implied compliance or clarify the
>absence of it.
>
>> Sure, knock yourself out.  I don't consider it more or less valid to
>> do so, but patches are welcome.
>
>Coming right up!
>
>> Definately keep the ability to support external setting of DT, as you
>> can't pass any validation tests without it.
>
>Yes, I've already figured that out when studying the impact of such a
>change.  Since there's already special-case handling of with/without
>a DT vector, that seemed the obvious thing to hook into.
>
>The two changes that affected callers, which I didn't feel very
>confident about my understanding of, were:
>1. Changing the recommended seed size, and
>2. Using actual random seed material.
>
>The other one, which I have to think *very* hard about, is whether
>using the same seed material as /dev/random in this much weaker
>cryptographic construction will introduce a flaw in *it*.

I have no idea what you are referring to here. The caller is requred to 
seed the DRNG. Typically that is done with a call to get_random_bytes. 
As Neil mentioned, the X9.31 DRNG implementation does not seed itself.

The get_random_bytes call has no relationship to /dev/random other than 
it pulls from the same noise source. It is highly related to 
/dev/urandom as it uses the same entropy pool and is nonblocking.

I would be very interested in cryptographic or entropy related concerns 
about this seeding approach.


Ciao
Stephan
-- 

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[George Spelvin]

>> The other one, which I have to think *very* hard about, is whether
>> using the same seed material as /dev/random in this much weaker
>> cryptographic construction will introduce a flaw in *it*.

> I have no idea what you are referring to here. The caller is requred to 
> seed the DRNG. Typically that is done with a call to get_random_bytes. 
> As Neil mentioned, the X9.31 DRNG implementation does not seed itself.

Er, yes it does.  Not the key, but the IV vector V[].

Here's the closest thing I can find on-line to a direct quote
from the ANSI Spec:

http://www.untruth.org/~josh/security/ansi931rng.PDF

"Let DT be a date/time vector which is updated on each iteration."

This timestamp is a source of continuous reseed material.  The spec
doesn't impose specific resolution requirements, but it's hopefully
obvious that the finer, the better.  The goal is a vector which changes
per iteration.

There are limitations due to its finite entropy and lack of catastrophic
reseeding, as Kelsey & Schneier pointed out:

https://www.schneier.com/paper-prngs.html

but it is intended as an entropy source.

Hopefully very soon I'll have a patch series to post.  (Unfortunately,
I just managed to oops my kernel and need to reboot to continue testing.)

If I don't do much more, it'll be patch 13/17 in the series.  I think
the use of get_random_int() is a good compromise between the raw
random_get_entropy() timestamp and the (too heavy) get_random_bytes().

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[Neil Horman]

On Mon, Dec 01, 2014 at 11:55:18PM -0500, George Spelvin wrote:
> >> The other one, which I have to think *very* hard about, is whether
> >> using the same seed material as /dev/random in this much weaker
> >> cryptographic construction will introduce a flaw in *it*.
> 
> > I have no idea what you are referring to here. The caller is requred to 
> > seed the DRNG. Typically that is done with a call to get_random_bytes. 
> > As Neil mentioned, the X9.31 DRNG implementation does not seed itself.
> 
> Er, yes it does.  Not the key, but the IV vector V[].
> 
> Here's the closest thing I can find on-line to a direct quote
> from the ANSI Spec:
> 
> http://www.untruth.org/~josh/security/ansi931rng.PDF
> 
> "Let DT be a date/time vector which is updated on each iteration."
> 
> This timestamp is a source of continuous reseed material.  The spec
> doesn't impose specific resolution requirements, but it's hopefully
> obvious that the finer, the better.  The goal is a vector which changes
> per iteration.
> 
That is an old version.  The updated version (published in 2005), and specified
in the ansi_cprng.c file removes that language.

> There are limitations due to its finite entropy and lack of catastrophic
> reseeding, as Kelsey & Schneier pointed out:
> 
> https://www.schneier.com/paper-prngs.html
> 
> but it is intended as an entropy source.
> 
Again, that language is removed in the more recent version.  Using DT as an
entropy source, and updating it on each iteration also destroys the predictive
nature of the cprng when two peers use it to communicate.  That is to say, if a
DT vector is updated every iteration, and the resultant R value is used as a key
to encrypt data, the validitiy of that key at a peer host using an identically
seeded cprng to decrypt is limited by the granularity of the DT value.  That is
to say, if you update DT every second in cprng, an entity that knows the secret
key can only decrypt that data up to a second after its encryption, unless the
decrypting entity also knows at exactly what time the data was encrypted.  If
you share the DT value, any entropy it provides becomes worthless, as it becomes
widely known.

The long and the short of it is that, if you want a cprng who's output can be
predicted by any entity with the IV and KEY values, then DT has to be known
initially and updated in a predictable fashion that is independent of the data
being transmitted.  Using a real date/time vector can't do that.

> Hopefully very soon I'll have a patch series to post.  (Unfortunately,
> I just managed to oops my kernel and need to reboot to continue testing.)
> 
> If I don't do much more, it'll be patch 13/17 in the series.  I think
> the use of get_random_int() is a good compromise between the raw
> random_get_entropy() timestamp and the (too heavy) get_random_bytes().
> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[George Spelvin]

> That is an old version.  The updated version (published in 2005), and
> specified in the ansi_cprng.c file removes that language.

Oh!  Thank you!  I'm pretty sure I read the 1998 version.

In fact, apparently there's a 2010 version:

http://www.codesdownload.org/3761-ANSI-X9-TR-31-2010.html

I need to figure out how to get my hands on that.

Presumably this is the 2005 version with the 2009 supplement incorporated.
If I could read Chinese, I might be able to find it here:

http://www.docin.com/p-524511188.html

> The long and the short of it is that, if you want a cprng who's output can be
> predicted by any entity with the IV and KEY values, then DT has to be known
> initially and updated in a predictable fashion that is independent of the data
> being transmitted.  Using a real date/time vector can't do that.

Er, yes, this is all extremely obvious; I'm not quite sure why we're
belabouring it.  Fully deterministic generators have their uses, which
is why I had to ask in the beginning what the design intent was.

If this is *intended* to be purely deterministic, there's nothing to fix.
I'd like to propose a small comment clarification because a quick reading
confused me.

But when I talked about making it random, you said "send a patch", so
I did.  If you don't want the semantic change, I'm not upset.  The other
code cleanups are hopefully (after I've finished polishing them) useful;
just stop before the whole "union block" business.

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[Stephan Mueller]

Am Samstag, 29. November 2014, 12:58:56 schrieb Neil Horman:

Hi Neil,

>On Fri, Nov 28, 2014 at 06:23:51PM -0500, George Spelvin wrote:
>> I've been trying to understand the crypto layer, and it's a bit of a
>> struggle because I'm trying to learn how it's supposed to work by
>> reading the code, and I keep finding code I want to fix.
>
>Patches welcome.
>
>> ansi_cprng.c is the current itch I'm eager to scratch.
>> 
>> Other than enough implementation stupidities to make me scream
>> (particularly the "rand_data_valid" variable name which is actually a
>
>Its actually a counter of the number of valid random data bytes in the
>buffer being returned to a caller, as well as an index into the
>internal buffer from which to draw fresh random data.  Sorry if you
>don't get that, but it seems pretty clear.
>
>> count of INvalid data, and  keeping 5 blocks of state, including
>> sensitive previous output, when only 3 are needed), one thing I
>> can't help noticing
>Not sure where you're getting that from, only 1 block of random data is
>stored at any one time to return to a caller
>
>> is that this is definitely NOT conformant with the X9.17/X9.31 spec.
>
>This is the document it was based of off:
>http://csrc.nist.gov/groups/STM/cavp/documents/rng/931rngext.pdf

As this implementation has successfully being checked with the FIPS 
140-2 reference implementation, we all must assume it is in total 
compliance with the spec.
>
>From my read, it seems to be in complete compliance.
>
>> That's because the spec requires a timestamp for each output block
>> to provide additional entropy, and a counter won't cut it.
>
>The document places no constrints on the value or progression of DT. 
>As such a counter is as valid as any other implementation.  You're
>welcome to enhance that however, as I said, patches welcome.
>
>> I'm fixing the obvious things, but on this point, I have two choices:
>> 
>> 1. Add some comments clarifying that the "Based on" part of the
>> header
>> 
>>    is anything but a claim of compliance; those specs are for an RNG,
>>    while this is a PRNG.
>
>Please read more closely, the header clearly states this is a PRNG
>implementation, and a quick google search of the terms in the header
>bring up the document referenced above, with which this cprng is in
>compliance with.
>>  And probably delete all the FIPS stuff, as
>>  
>>    there's no spec to claim compliance with.  Or
>
>Maybe do some research before making big claims like this:
>http://csrc.nist.gov/publications/fips/fips140-2/fips1402annexc.pdf

Supporting to that is FIPS 140-2 standard section 4.9.2 which requires 
the continuous self test.
>
>Its just a draft, but digging through the NIST site will bring up the

It is kept draft deliberately to allow NIST to make changes without some 
government big-wig to sign up on it (and cause a delay of a couple of 
years.

>approved version.  Both show that a 3 DES CPRNG based on ANSI X9.31 is
>valid, and provides  a reference to the paper above as the
>implementation guideline.
>> 2. Fix the code to use random_get_entropy() and jiffies for the
>> 
>>    DT seed vector.
>
>Sure, knock yourself out.  I don't consider it more or less valid to do
>so, but patches are welcome.

There is NO need for additional entropy at this point as the X9.31 DRNG 
does not claim prediction resistance with a constant reseeding.
>
>> In the latter case, I'd have to leave the current deterministic code
>> as an option for self-testing, but I'd drop the recommended seedsize
>> to DEFAULT_PRNG_KSZ + DEFAULT_BLK_SZ (one key and one IV), and have
>> an internal flag indicating whether to use an incrementing DT vector
>> or generate it fresh.
>
>Yup.  Strictly speaking the API is in-kernel only, so you don't really
>have to worry about handling backwards compatibility, but if you don't
>allow for DT to be specified as an initial value, you won't be able to
>validate against any of the test vectors that NIST provides:
>http://csrc.nist.gov/groups/STM/cavp/documents/rng/RNGVS.pdf
>
>I will also point out that CPRNG's are designed such that peers
>communicating with a cprng are expected to be able to predect the
>cprng output, which implies that the DT value needs to remain
>predictable as well.  Using an actual date time vector is going to
>make communication like that very unstable if there is even a little
>clock drift on either system.  As such, while its less entropy, using
>a simple arbitrary vector with an increment on each random data
>generation leads to greater stability and predictability for those
>with the key.  The data provided in the validation test in Appendix
>B.1.5 of the above document supports that, as the DT value is
>arbitrary and incremented by one on each iteration.
>> If some code (like the current self-test code) provides an extra
>> DEFAULT_BLK_SZ of seed material, it would go into determinsitic mode,
>> but if it's missing, DT would be generated dynamically.
>
>Sure, patches welcome.
>
>> But that's a question of design intent, and I can't intuit that from
>> the code.  Can someome enlighten me as to which option is preferred?
>Definately keep the ability to support external setting of DT, as you
>can't pass any validation tests without it.


Ciao
Stephan
-- 

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[Stephan Mueller]

Am Freitag, 28. November 2014, 18:23:51 schrieb George Spelvin:

Hi George,

>I've been trying to understand the crypto layer, and it's a bit of a
>struggle because I'm trying to learn how it's supposed to work by
>reading the code, and I keep finding code I want to fix.

See Documentation/DocBook/crypto-API.tmpl in the cryptodev-2.6 tree. 
There you will find tons of documentation (which will be merged during 
3.19-rc1)

Ciao
Stephan
-- 

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[George Spelvin]

> See Documentation/DocBook/crypto-API.tmpl in the cryptodev-2.6 tree. 
> There you will find tons of documentation (which will be merged during 
> 3.19-rc1)

Yes, I've been reading that.  It certainly helps a great deal, but
still leaves me with some significant questions.

I started researching the crypto layer when I proposed using Dan
Bernstein's SipHash elsewhere in the kernel and someone asked for a
crypto API wrapper for it.  That seemed a simple enough request to me,
but it's been a deeper rabbit hole than I expected.

I started reading the code to another keyed hash, michael_mic, as a model,
but I'm stil trying to understand the intended difference between "struct
crypto_shash" and "struct shash_desc", and in particular why both have
a copy of the key.  The SHASH API documentation at

https://git.kernel.org/cgit/linux/kernel/git/herbert/cryptodev-2.6.git/tree/include/crypto/hash.h

isn't particularly enlightening.  If the crypto_shash were entirely
read-only and the shash_desc were the entire volatile state, that would
make sense, but as it is I'm confused about the design intent.

(On a related point, the general lack of const declarations throughout the
crypto layer has been a source of frustration.)


The other big issue I'm struggling with is how to get the tcrypt.ko module
to print "ansi_cprng has passed its tests."  All it has produced for me
so far is a few kilobytes of dmesg spam about ciphers which aren't even
configured in my kernel.

After a few hours of trying to figure out what the alg and type parameters
do, I gave up and cut and pasted the tests into prng_mod_init().

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[Neil Horman]

On Tue, Dec 02, 2014 at 12:39:30AM -0500, George Spelvin wrote:
> > See Documentation/DocBook/crypto-API.tmpl in the cryptodev-2.6 tree. 
> > There you will find tons of documentation (which will be merged during 
> > 3.19-rc1)
> 
> Yes, I've been reading that.  It certainly helps a great deal, but
> still leaves me with some significant questions.
> 
> I started researching the crypto layer when I proposed using Dan
> Bernstein's SipHash elsewhere in the kernel and someone asked for a
> crypto API wrapper for it.  That seemed a simple enough request to me,
> but it's been a deeper rabbit hole than I expected.
> 
> I started reading the code to another keyed hash, michael_mic, as a model,
> but I'm stil trying to understand the intended difference between "struct
> crypto_shash" and "struct shash_desc", and in particular why both have
> a copy of the key.  The SHASH API documentation at
> 
> https://git.kernel.org/cgit/linux/kernel/git/herbert/cryptodev-2.6.git/tree/include/crypto/hash.h
> 
> isn't particularly enlightening.  If the crypto_shash were entirely
> read-only and the shash_desc were the entire volatile state, that would
> make sense, but as it is I'm confused about the design intent.
> 
Not sure what you're concerned about, or what you're even referencing.  A
struct crypto_shash is the object retured by crypto_alloc_shash, and represents
an instance of a synchronous hash algorithm:
struct crypto_shash {
        unsigned int descsize;
        struct crypto_tfm base;
};

The key is stored in the base.__crt_ctx part of the structure in a algorithm
specific manner.

The shash_desc structure represents a discrete block of data that is being
hashed.  It can be updated with new data, reset, finalized, etc.  It only points
to the crypto_hash structure that it is associated with (as it must, given that
the crypto layer needs to know what algorithm to use to hash the data and what
key to use).  But it doesn't store a second copy of the key on its own.

> (On a related point, the general lack of const declarations throughout the
> crypto layer has been a source of frustration.)
> 
So fix it.  Making large claims about what frustrates you about the code without
producing any fixes doesn't make people listen to you.
> 
> The other big issue I'm struggling with is how to get the tcrypt.ko module
> to print "ansi_cprng has passed its tests."  All it has produced for me
> so far is a few kilobytes of dmesg spam about ciphers which aren't even
> configured in my kernel.
> 
The tests only print out a pass fail notification in fips mode, that seems
pretty clear if you look at the alg_test function.

> After a few hours of trying to figure out what the alg and type parameters
> do, I gave up and cut and pasted the tests into prng_mod_init().

They're used to differentiate algorithms that can be used for multiple purposes.
See the CRYPTO_ALG_TYPE_* defines in crypto.h.  For the CPRNG, they do nothing
since an RNG is only an RNG.

> --
> To unsubscribe from this list: send the line "unsubscribe linux-crypto" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> 

Re: Is ansi_cprng.c supposed to be an implmentation of X9.31?

[George Spelvin]

> Not sure what you're concerned about, or what you're even referencing.

Sorry for the confusion, but it's genuine.  See below for what I think is
the solution.

> The shash_desc structure represents a discrete block of data that is
> being hashed.  It can be updated with new data, reset, finalized, etc.
> It only points to the crypto_hash structure that it is associated with
> (as it must, given that the crypto layer needs to know what algorithm
> to use to hash the data and what key to use).  But it doesn't store a
> second copy of the key on its own.

Er, I saw the following code:

static int michael_setkey(struct crypto_shash *tfm, const u8 *key,
			  unsigned int keylen)
{
	struct michael_mic_ctx *mctx = crypto_shash_ctx(tfm);

	const __le32 *data = (const __le32 *)key;

	if (keylen != 8) {
		crypto_shash_set_flags(tfm, CRYPTO_TFM_RES_BAD_KEY_LEN);
		return -EINVAL;
	}

	mctx->l = le32_to_cpu(data[0]);
	mctx->r = le32_to_cpu(data[1]);
	return 0;
}

and thought "okay, the key is in mctx->l and mctx->r."

Then I saw

static int michael_init(struct shash_desc *desc)
{
	struct michael_mic_desc_ctx *mctx = shash_desc_ctx(desc);
	struct michael_mic_ctx *ctx = crypto_shash_ctx(desc->tfm);
	mctx->pending_len = 0;
	mctx->l = ctx->l;
	mctx->r = ctx->r;

	return 0;
}

and thought "the key is being copied from the ctx to the desc.  Why
the heck are they doing it in two steps?"

I spent a long time trying to figure out why there were two separate
layers, as it looked like

struct michael_mic_ctx {
	u32 l, r;
};

was a strict subset of

struct michael_mic_desc_ctx {
	u8 pending[4];
	size_t pending_len;

	u32 l, r;
};

and thus the former was unnecessary.

(Another code optimization that jumps out at me: given that pending_len
is strictly between 0 and 3, using a 64-bit size_t unnecessarily bloats
the context structure to 24 bytes.  Shrinking it to 32 bits would reduce
the context to 16 bytes, and given that at most three bytes of pending[]
are ever used, except transiently in the update() function, pending_len
could be stored in pending[3] and and the context shrunk to 12 bytes.)


I'm thinking that the confusion comes from my unfortunate choice of
which file to start reading and the peculiar way that michael_mic's key
is more like an IV, so there is neither key scheduling nor persistent
access to it.


== My guess as to how this works ==

(If I say anything wrong, please correct me!)

A ctx is an abstraction of a (scheduled) key.  With symmetric ciphers,
it's very common to have a complex key set up (I'm looking at you, twofish)
which can be re-used for multiple messages/packets/whatever.

It has to be an opaque object because it might correspond to some
state in a hardware acclerator, with the software swapping keys in
and out like virtual memory.

A desc is the abstraction of an IV.  It handles chaining and block
boundaries, to encrypt/hash/transform a stream/bvec/sk_buff of data.

The reason for the separation is that multiple descs may simultaneously
access the same ctx.

This is okay because the ctx reference is conceptually read-only.
(If there's swapping of hardware contexts going on behind the curtain,
the ctx may not be entirely immutable, but it's like a cache: you're
not supposed to notice the difference.)

There are some cases, like ECB, where a desc is a ridiculously thin
wrapper and seems like overkill, but it's there to provide a consistent
interface.

(Design choice: a single ctx can handle both encryption and decryption.
For algorithms that have different key schedules for the two directions,
it has to waste the space even if the cipher is only being used forward.)

>> (On a related point, the general lack of const declarations throughout the
>> crypto layer has been a source of frustration.)
 
> So fix it.  Making large claims about what frustrates you about the
> code without producing any fixes doesn't make people listen to you.

I'm happy to!  It's just a large, invasive, change and I wonder how welcome
it is.  Maybe there's a reason for the omission that I'm not seeing?

You know the aphorism "never attribute to malice that which can be
adequately explained by stupidity"?  Well, there's a follow-on, which
says be careful attributing to someone else's stupidity that which
can be adequately explained by your own.

It's a pattern I go through frequently, and I think others do too:
my initial reaction is "what the @#$@# is this $#!+?", but I try to
consider whether the fault is actually mine before speaking aloud (or
hitting "send", as the case may be).

If it's soemthing that annoys you too and you just haven't gotten around
to fixing it, I'd be delighted!

I just wanted to start with something smaller in scope, confined to
a single source file, where I felt like I understood the implications
better.

>> The other big issue I'm struggling with is how to get the tcrypt.ko module
>> to print "ansi_cprng has passed its tests."  All it has produced for me
>> so far is a few kilobytes of dmesg spam about ciphers which aren't even
>> configured in my kernel.

> The tests only print out a pass fail notification in fips mode, that seems
> pretty clear if you look at the alg_test function.

There are two major call paths from tcrypt_mod_init.

tcrypt_mod_init
-> do_alg_test
   -> crypto_has_alg
      -> crypto_alg_mod_lookup
         -> crypto_larval_lookup

tcrypt_mod_init
-> do_test
   -> tcrypt_test
      -> alg_test
         -> alg_find_test
         -> alg_test_cipher
         -> alg_test_descs[i].test
            -> alg_test_{aead,cipher,skcipher,comp,pcomp,hash,crc32c,...}

The second path, which seems to be broad testing, doesn't seem to print
anything on success, but I was hoping there was something on the first
path if I asked for a specific algorithm.  But that code path led me
far outside the "test" source files and I got lost chasing call chains
trying to find actual tests.

Hopefully you can see how, starting from the top, one might hope that
the first call path would lead to a single-algorithm test, which might
print more detailed informations.

I added a printk to alg_test_cprng() and got that to print after a while.
I just had so many errors in the logs about

> alg: hash: Failed to load transform for wp512: -2
> alg: hash: Failed to load transform for wp384: -2
> alg: hash: Failed to load transform for wp256: -2
> alg: skcipher: Failed to load transform for ecb(tnepres): -2
> alg: skcipher: Failed to load transform for ecb(anubis): -2
> alg: skcipher: Failed to load transform for cbc(anubis): -2
> alg: hash: Failed to load transform for tgr192: -2
> alg: hash: Failed to load transform for tgr160: -2
> alg: hash: Failed to load transform for tgr128: -2
> alg: skcipher: Failed to load transform for pcbc(fcrypt): -2
> alg: skcipher: Failed to load transform for ecb(camellia): -2

That I wasn't sure it if it actually ran the test I wanted, or had
already bailed out due to too many errors.