[openssl-dev] [openssl.org #4626] Re: Are the point-at-infinity checks in ecp_nistz256 correct?

[Brian Smith via RT]

Brian Smith  wrote:
> The issue is particularly clear when we multiply the generator by
> zero. Note that in general, an application shouldn't multiply the
> generator by zero since there's no useful cryptographic purpose for
> doing so. But, this is a convenient example.

Sorry, I was wrong. From the definition of ECDSA:

H = Hash(M).
Convert the bit string H to an integer e.
w = s**−1 mod n
u1 = (e * w) mod n
R = u1*G + u2*Q

If the highest 256 bits of Hash(M) are zero, then e == 0 and then u1
== 0 * w == 0. So, it probably is important to handle g_scalar == 0 in
the way I described in my earlier message, using the conditional copy.

Cheers,
Brian


-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4626
Please log in as guest with password guest if prompted

-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

[openssl-dev] [openssl.org #4625] Re: Are the point-at-infinity checks in ecp_nistz256 correct?

[Brian Smith via RT]

The issue is particularly clear when we multiply the generator by
zero. Note that in general, an application shouldn't multiply the
generator by zero since there's no useful cryptographic purpose for
doing so. But, this is a convenient example.

In the code we have,

ecp_nistz256_gather_w7(, preComputedTable[0], wvalue >> 1);
ecp_nistz256_neg(p.p.Z, p.p.Y);
copy_conditional(p.p.Y, p.p.Z, wvalue & 1);
memcpy(p.p.Z, ONE, sizeof(ONE));

The generator is all zeros, so we'll start off with the point (0, 0,
1). Then we add the point at infinity over and over again, leaving
that point unchanged each time. Thus, we'll end with (0, 0, 1). Then:

r->Z_is_one = is_one(p.p.Z) & 1;

Thus, the resulting point will be (0, 0, 1).

After the memcpy quoted above, we need to do a copy_conditional(p.p.Z,
is_infinity, ZERO) or equivalent, where ZERO is all-zeros and where
is_infinity is the result of checking if (x, y) == (0, 0).

This is just one example of an edge case that is handled in a
surprising way. I think there are more, as described in the quoted
message below.

Cheers,
Brian


Brian Smith  wrote:
>
> Brian Smith  wrote:
>>
>> When doing math on short Weierstrass curves like P-256, we have to
>> special case points at infinity. In Jacobian coordinates (X, Y, Z),
>> points at infinity have Z == 0. However, instead of checking for Z ==
>> 0, p256-x86-64 instead checks for (X, Y) == (0, 0). In other words, it
>> does, in some sense, the opposite of what I expect it to do.
>
>
> I exchanged email with both of the original authors of the code, Shay and 
> Vlad. He that the ecp_nistz256_point_* functions indeed intend to represent 
> the point at infinity as (0, 0) and it is expected (but I did not verify) 
> that those functions should work when the point at infinity is encoded as (0, 
> 0, _).
>
>> The authors
>> instead decided to encode the point at infinity as (0, 0), since the
>> affine point (0, 0) isn't on the P-256 curve. It isn't clear why the
>> authors chose to do that though, since the point at infinity doesn't
>> (can't, logically) appear in the table of precomputed multiples of G
>> anyway.
>
>
> Actually, as the code says, the point at infinity implicitly occurs in the 
> table implicitly. Obviously the accumulator point will be at infinity until 
> at least a one bit is found in the scalar.
>
>>
>> But, it seems like the functions that do the computations, like
>>
>> ecp_nistz256_point_add and ecp_nistz256_point_add_affine, output the
>> point at infinity as (_, _, 0), not necessarily (0, 0, _). Also,
>> ecp_nistz256's EC_METHOD uses ec_GFp_simple_is_at_infinity and
>> ec_GFp_simple_point_set_to_infinity, which represent the point at
>> infinity with z == 0, not (x, y) == 0. Further ecp_nistz256_get_affine
>> uses EC_POINT_is_at_infinity, which checks z == 0, not (x, y) == 0.
>> This inconsistency is confusing, if not wrong. Given this, it seems
>> like the point-at-infinity checks in the ecp_nistz256_point_add and
>> ecp_nistz256_point_add_affine code should also be checking that z == 0
>> instead of (x, y) == (0, 0).
>
>
> Instead, when we convert a point from EC_POINT to P256_POINT or 
> P256_POINT_AFFINE, we should translate the (_, _, 0) form into the (0, 0, 0) 
> form. And/or reject points at infinity as inputs to the function. Similarly, 
> when we convert the resultant P256_POINT to an EC_POINT, we chould translate 
> the (0, 0) encoding of the point at infinity to the (0, 0, 0) form or at 
> least the (_, _, 0) form.
>
> In particular, consider the case where you have an EC_POINT that isn't at 
> infinity, e.g. (x, y, 1). Then you call EC_POINT_set_to_infinity on it. Then 
> it is (x, y, 0). Then you pass it to EC_POINT_mul/EC_POINTs_mul even though 
> you shouldn't.
>
> Maybe the precondition of EC_POINT_mul/EC_POINTs_mul is that none of the 
> input points are at infinity, in which case it doesn't matter. (But if so, 
> maybe these functions should do a point-at-infinity check.) But if it is 
> allowed to pass in the point at infinity, then the ecp_nistz256 code should 
> translate the input point from (_, _, 0) form to (0, 0, _) form before doing 
> the computation. It can use is_zero and copy_conditional and friends to do 
> this.
>
> Similarly, after the computation, it should translate the (0, 0, _) form to 
> (_, _, 0) form. In particular, it should do such a translation before the 
> code sets Z_is_one, AFAICT. Note that the nistz256 code might be using the 
> form (0, 0, 0) instead of (0, 0, _) in which case this translation might not 
> be necessary.
>
> Regardless, it would be useful to write tests for these cases:
> 1. Verify that the result is correct when any of the input points are (0, 0, 
> 0)
> 2. Verify that the result is correct when any of the input points are (_, _, 
> 0).
> 3. Verify that the result is correct, and in particular that Z_is_one is set 
> correctly on the result, when the final result is at 

Re: [openssl-dev] [openssl.org #4621] BUG: nistz256 point addition check for a = +/-b doesn't work for unreduced values

[Brian Smith via RT]

Brian Smith via RT <r...@openssl.org> wrote:

> Finally, as I mentioned on the mailing list, it seems the function is_zero
> is missing a comparison of the last limb in the 32-bit case.
>

And of course, when I said "is_zero" I meant "is_one":
https://github.com/openssl/openssl/blob/aa6bb1352b1026b20a23b49da4efdcf171926eb0/crypto/ec/ecp_nistz256.c#L226



-- 
https://briansmith.org/

-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4621
Please log in as guest with password guest if prompted

-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

[openssl-dev] [openssl.org #4621] BUG: nistz256 point addition check for a = +/-b doesn't work for unreduced values

[Brian Smith via RT]

I verified with the authors of the nistz256 code that all the arithmetic is
done mod P256 (P), but the results might be unreduced if they are less than
2**256. Thus, all the arithmetic must handle the cases where its inputs are
in the range [0, 2**256 - 1], not just [0, P). And, it must deal with the
cases where some values have multiple representations. For example, the
value 0 can be represented as either 0 or P + 0, 1 can be represented
either as 1 or as P + 1, etc.

The nistz256 code contains code that looks like this:

  if (is_equal(U1, U2) && !in1infty && !in2infty) {
if (is_equal(S1, S2)) {
...
}
  }

This code only works for values that have one representation; it doesn't
work for all values. For example, consider U1 == 1, U2 = P + 1. Then,
is_equal(U1, U2) returns false, but in fact U1 == U2 (mod P). Thus, we
should run the code for the exceptional case (doubling or setting to the
point at infinity), but actually we just keep going with a normal addition.

You can see that the code in ecp_nistp256 and ecp_nistp224 such as
`is_zero` handles this correctly by considering both representations of 0:
0 and P + 0.

To fix this, a constant-time conditional subtraction of P should be done on
U1 and U2, and a conditional subtraction should also be done on S1 and S2.
I discussed this with some other people familiar with the code and they
agree that this seems to be a good way to do it.

Note again that it is possible for the value 0 to be represented as either
0 or as P + 0. This brings into question whether is_zero is correct,
because it doesn't consider P to be zero. Here there was some disagreement
about whether it is necessary to check for P. I personally think that it is
safer to check for both 0 and P like the nistp256 code does, because I it
is hard to make a proof that the values cannot be P.

Not also again that the value 1 can be represented as 1 or as P + 1. Thus,
the statement Z_is_one = is_one(...); appears to also be wrong, or at least
not obviously correct.

Finally, as I mentioned on the mailing list, it seems the function is_zero
is missing a comparison of the last limb in the 32-bit case.

Unfortunately, I don't have any test vectors for triggering any bugs that
would serve as a basis of regression tests; these were found from reading
the code.

Cheers,
Brian
-- 
https://briansmith.org/

-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4621
Please log in as guest with password guest if prompted

-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

Re: [openssl-dev] [openssl.org #4362] chacha-x86.pl has stricter aliasing requirements than other files

[Brian Smith via RT]

Brian Smith  wrote:
> It seems that 32-bit ARM has the same limitation as x86 that the input and
> output pointers must match or the input and output buffers must not overlap
> at all. I'm not sure which ARM code path (NEON or non-NEON, or both) has
> this issue.

Just to follow up on this: I think this might actually be a QEMU ARM
(32-bit) emulator bug, or a configuration issue on my part. In one
version of the QEMU emulator, I have no trouble. But, in another,
newer, version of the QEMU emulator, I get results like this for
BoringSSL's chacha_test (modified to print all the results before
failing):

Mismatch at length 64 with in-place offset 1.
Mismatch at length 64 with in-place offset 2.
Mismatch at length 64 with in-place offset 5.
Mismatch at length 64 with in-place offset 6.
Mismatch at length 64 with in-place offset 9.

Notice, in particular, that it only happens when the input length is
64, and only for specific offsets. Like I said, I consistently get
these failures on the Android emulator but not in a newer version of
QEMU. It doesn't make any difference whether NEON is enabled or
disabled; I believe this is because the ARM code only uses NEON if
there are at least 3 blocks.

Anyway, I see in the ARM chacha code that there is a special case when
the length is 64, so it might be worth double-checking that code.

Just FYI.


-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4362
Please log in as guest with password guest if prompted

-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

Re: [openssl-dev] [openssl.org #3502] nameConstraints bypass bug

[Brian Smith via RT]

Salz, Rich via RT  wrote:

> > Note that other implementations treated this as a bug and fixed it a
> long time
> > ago.
>
> What other implementations, and what did they do?  Always treating a CN as
> a DNS name?  We can't.
>

As one example, mozilla::pkix treats the CN as a dNSName/iPAddress iif
there is no subjectAltName extension and iif the CN is a valid
dNSNa/iPAddress syntactically.


> Applications can do that now by setting the right flag, as Viktor pointed
> out.  I think it's too late to make the default change for 1.1
>

The important thing is: What happens when applications use the default
settings? If the default settings are "don't consider the subject CN for
name constraint processing, but do consider it for name validation" then
that's obviously wrong and dangerous.

Besides that, there needs to be a way to make name constraint processing
consistent with name validation. That means that if name validation is
configured (by default or with a switch) to look at subject CNs then the
name constraints need to be configurable to do the same. Name validation
and name constraint validation go hand-in-hand.


> > How about this for a heuristic:  If nameConstraints are in effect, then
> the
> > validator MUST NOT accept the CN as a DNS name.  This seems like the
> least
> > the validator could do, in light of the aforementioned deprecation.
>
> Probably.
>

If the validator has that much information then it should be simple for it
to keep the state in sync. But, often (usually?) certificate chain
validation and certificate name validation are done in separate steps by
applications, and it's difficult or impossible to keep things in sync in
that case.


> >  -- The problem is not solved until bad guys are
> >   /required/ to use SAN;
>
> Applications can make that happen now.


Again, what matters is less what applications *can* do and more what
applications *actually* do. I suspect that most applications are having the
wrong, dangerous, thing happen. In fact, that is almost definitely the
case, considering that many applications are doing their own name
validation (and thus almost definitely looking at the subject CN as that is
historically how it is done), as OpenSSL didn't provide a name validation
API until recently.

So, I agree with the others that OpenSSL is broken in this respect.

Cheers,
Brian
-- 
https://briansmith.org/

-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=3502
Please log in as guest with password guest if prompted

-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

Re: [openssl-dev] [openssl.org #4362] chacha-x86.pl has stricter aliasing requirements than other files

[Brian Smith via RT]

It seems that 32-bit ARM has the same limitation as x86 that the input and
output pointers must match or the input and output buffers must not overlap
at all. I'm not sure which ARM code path (NEON or non-NEON, or both) has
this issue.

Cheers,
Brian
-- 
https://briansmith.org/

-- 
Ticket here: http://rt.openssl.org/Ticket/Display.html?id=4362
Please log in as guest with password guest if prompted

-- 
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

Re: [openssl-dev] [openssl.org #4116] [PATCH] Reimplement non-asm OPENSSL_cleanse()

[Brian Smith via RT]

Alessandro Ghedini via RT  wrote:

> I was also wondering whether it would make sense to just drop the asm
> implementations. Does the speed-up justify the added complexity?
>

IMO, it should work like this:
* memset_s when memset_s is available.
* Otherwise, SecureZeroMemory, when SecureZeroMemory is available.
* Otherwise, if a flag OPENSSL_REQUIRE_SECURE_ZERO is set, fail.
* Otherwise, use an assembly language implementation, if available.
* Otherwise, emit a warning and use the C implementation.

Note in particular that the C compiler is allowed to completely defeat the
purpose of the function unless SecureZeroMemory or memset_s is used, even
if you use "volatile" or other tricks. The primary purpose of the assembly
language implementations is to reduce the possibility that the C compiler
will do the weird things that C compilers love to do.

Cheers,
Brian
-- 
https://briansmith.org/

___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

Re: [openssl-dev] [openssl.org #4116] [PATCH] Reimplement non-asm OPENSSL_cleanse()

[Brian Smith via RT]

On Sat, Oct 31, 2015 at 11:50 AM, Alessandro Ghedini via RT 
wrote:

> In any case memset_s is not available anywhere anyway, so that doesn't
> really
>
matter.
>

Is it available in some places, e.g.
https://developer.apple.com/library/mac/documentation/Darwin/Reference/ManPages/man3/memset_s.3.html
.


> > * Otherwise, SecureZeroMemory, when SecureZeroMemory is available.
> > * Otherwise, if a flag OPENSSL_REQUIRE_SECURE_ZERO is set, fail.
>
> In 99% of the cases (e.g. Linux with glibc or any *BSD) that would fail,
> so I
> don't see the point in that.
>

The point is to let the person building OPENSSL say "I want the build to
fail if there isn't a secure way to zero memory, because I'm expecting
there to always be one in my configuration." Alternatively, there could be
an OPENSSL_USE_MEMSET_S flag that says "always use memset_s and never
anything else."


> > Note in particular that the C compiler is allowed to completely defeat
> the
> > purpose of the function unless SecureZeroMemory or memset_s is used, even
> > if you use "volatile" or other tricks.
>
> I don't think that is true (regarding the volatile pointer). But assuming
> that
> a broken compiler decided to optimize that call away, what's stopping it to
> optimize the call to the asm implementation as well? Also, such broken
> compiler
> probably wouldn't know about C11 either, so even if memset_s() was
> available it
> could optimize that as well.
>

Such optimizations are legal. Otherwise, C11 wouldn't have defined
|memset_s|. And, the entire purpose of |memset_s| is to disable such
optimizations.


> I don't know how compilers are supposed to treat memset_s(), but if I
> define a
> memset_s() function which just calls memset() internally, GCC (v5.2.1
> 20151028)
> optimizes that away just as it does with plain memset(), so libc
> implementations would probably need to adopt "tricks" to avoid the
> optimization
> as well.
>

Right. It has to be built into the compiler.


> FWIW OpenSSH implements the portable explicit_bzero() using the volatile
> pointer as well (unless memset_s() is detected at build time).


That is similar to what I'm suggesting.


> On OpenBSD it
> just uses OpenBSD's explicit_bzero() which is implemented using memset()
> and a
> weak function pointer.


It is a good idea to detect OpenBSD at compile time and use
|explicit_bzero|, just like for |SecureZeroMemory| on Windows.

Don't pay much attention to what tricks OpenBSD's |explicit_bzero| uses.
Those tricks are not guaranteed to work for anything other than that one
function on OpenBSD.


> But that (as used in LibreSSL) seems to have problems in
> relation to LTO, unless optimizations are specifically disabled:
> https://github.com/libressl-portable/openbsd/issues/5


Right, this is more evidence that the only correct implementation is to use
a compiler-provided |memset_s|, |explicit_bzero|, |SecureZeroMemory|. It is
not possible to implement your own in a way that is guaranteed to work. If
you need to implement your own.



> On the other hand BoringSSL uses memset() with an explicit memory barrier
>

The explicit memory barrier is bad for performance.

And, it also isn't guaranteed to work. I don't speak for the BoringSSL
team, but in correspondence with them, they don't seem to care much if
OpenSSL_cleanse works or if it is used.


> > The primary purpose of the assembly language implementations is to
> reduce the
> > possibility that the C compiler will do the weird things that C
> compilers love
> > to do.
>
> According to the changelog and git log, the primary purpose of the asm
> implementations was to improve performance (see commit b2dba9b). Using the
> volatile pointer implementation would IMO make these optimizations useless,
> hence the proposal to drop them and make things simpler.


Sorry. Instead of "primary purpose" (which implies intent), I should have
said 'primary advantage".  An assembly language implementation is more
likely to work than a C implementation because the C compiler generally
won't analyze externally-assembled code, so it has to assume that the
externally-assembled code has side effects, so it must call the
externally-assembled code. In theory, it is possible for the assembler, C
compiler, and the linker to work together during LTO and figure out that
the assembly language implementation doesn't have any side effects other
than zeroing memory, but that seems unlikely--much less likely than the C
compiler subverting any trick.

Note that sometimes I notice places that OpenSSL doesn't call
OPENSSL_cleanse when it seems like it would be warranted to be consistent
with other code. ecdh_compute_key [1] is one example. Generally, I don't
expect OpenSSL to (securely) zero memory, so it doesn't matter much to me.
But, if it matters to others, then this is something that would require an
substantial amount of auditing and fixing.

[1]

Re: [openssl-dev] [openssl.org #3721] Patch for additional checking of self-signed certificates

[Brian Smith via RT]

Short, Todd via RT r...@openssl.org wrote:
 Check that in matching issuer/subject certs, that a self-signed subject also 
 has a self-signed issuer.
 Given that the subject certificate is self-signed, it means that the issuer 
 and the subject are the same certificate. This change verifies that.

 Github link:
 https://github.com/akamai/openssl/commit/faff94b732472616828fe724e09053f134ebb88b

Could you explain this more?

In your patch, there is a comment that says Input certificate
(subject) is self signed. But, the test is that the issuer name
equals the subject name. That means the certificate is self-*issued*,
not self-*signed*.

Consider this chain:

{ Subject=Foo, Issuer=Foo, Key=Key1, Signed by Key2 }
{ Subject=Foo, Issuer=Foo, Key=Key2, Signed by Key3 }
{ Subject=Foo, Issuer=Foo, Key=Key3, Signed by Key3, Trust Anchor }

All three certificates are self-issued. The issuer of the first
certificate is not self-signed but it is self-issued. But, it being
self-issued doesn't matter because it isn't a trust anchor.

Consider this chain:

{ Subject=Foo, Issuer=Foo, Key=Key1, Signed by Key1 }
{ Subject=Foo, Issuer=Bar, Key=Key1, Signed by Key2 }
{ Subject=Bar, Issuer=Bar, Key=Key2, Signed by Key2, Trust Anchor }

The first certificate is self-signed and self-issued. It's issuer is
not self-signed or self-issued, so your patch would reject this chain.
But, this is a valid chain.

Cheers,
Brian


___
openssl-dev mailing list
To unsubscribe: https://mta.openssl.org/mailman/listinfo/openssl-dev

[openssl.org #1680] Possible Bug: x509_name_ex_d2i segmentation fault under IA-64

[Brian Smith via RT]

Detail:
When writing a function to generate a CSR via OpenSSL on IA-64, the
X509_REQ_set_subject_name function eventually calls x509_name_ex_d2i which
causes a segmentation fault under IA-64. This code works properly on
Solaris, IRIX, win32 (cygwin), and x86_64

Additional Details:
OpenSSL compiled debug allows the function to operate properly without
crashing
Inserting printf(here) statements between lines of x509_name_ex_d2i also
allows the function to operate without seg fault when built normally

Possibly Known Related Cases:
http://www.mail-archive.com/openssl-dev@openssl.org/msg20993.html

Test Setup:

Linux 2.6.5-7.252.PTF-sn1 SMP
Openssl 0.9.7m Configured linux-ia64 -fPIC
gcc version 3.3.3 (SuSE Linux)

GDB Dump:

Program received signal SIGSEGV, Segmentation fault.

0x400a58c0 in x509_name_ex_d2i ()

(gdb) where

#0  0x400a58c0 in x509_name_ex_d2i ()

#1  0x400ad1f0 in ASN1_item_ex_d2i ()

#2  0x400ae1a0 in ASN1_item_d2i ()

#3  0x4011a860 in ASN1_item_dup ()

#4  0x400a5b90 in X509_NAME_dup ()

#5  0x400a5cb0 in X509_NAME_set ()

#6  0x400bd760 in X509_REQ_set_subject_name ()



Thanks,

Brian Smith

Detail:
When writing a function to generate a CSR via OpenSSL on IA-64, the X509_REQ_set_subject_name function eventually calls x509_name_ex_d2i which causes a segmentation fault under IA-64. This code works properly on Solaris, IRIX, win32 (cygwin), and x86_64


Additional Details:
OpenSSL compiled debug allows the function to operate properly without crashing
Inserting printf(here) statements between lines of x509_name_ex_d2i also allows the function to operate without seg fault when built normally

Possibly Known Related Cases:
http://www.mail-archive.com/openssl-dev@openssl.org/msg20993.html

Test Setup:

Linux 2.6.5-7.252.PTF-sn1 SMP
Openssl 0.9.7m Configured linux-ia64 -fPIC
gcc version 3.3.3 (SuSE Linux)

GDB Dump:

Program received signal SIGSEGV, Segmentation fault.
0x400a58c0 in x509_name_ex_d2i ()
(gdb) where
#0 0x400a58c0 in x509_name_ex_d2i ()
#1 0x400ad1f0 in ASN1_item_ex_d2i ()
#2 0x400ae1a0 in ASN1_item_d2i ()
#3 0x4011a860 in ASN1_item_dup ()
#4 0x400a5b90 in X509_NAME_dup ()
#5 0x400a5cb0 in X509_NAME_set ()
#6 0x400bd760 in X509_REQ_set_subject_name ()

Thanks,
Brian Smith