Should Ada runtime provide special primitives for cryptography?

Should Ada runtime provide special primitives for cryptography?

[Natasha Kerensikova]

Hello,

I recently thought that Ada general strictness and integration with
proof systems would make it a good language for cryptographic
primitives.

However, when actually implementing cryptographic stuff, cleverness from
compiler and optimizer are often enemies. For example, overwriting a
buffer with zeroes might be optimized out when the buffer is not
accessed again.

I believe it would not be difficult for a compiler vendor to provide, as
part of the runtime, a zeroing procedure guaranteed to not be optimized
away, a (generic) array comparison guaranteed to execute in a constant
number of operations and/or branches, etc. And such subprograms would be
difficult to write externally, and the guarantees difficult to make
without tight compiler integration.

Would it be useful to propose an AI for the addition of such subprograms
to Ada standard library?



Natasha

Re: Should Ada runtime provide special primitives for cryptography?

[Dirk Heinrichs]

Natasha Kerensikova wrote:

> However, when actually implementing cryptographic stuff, cleverness from
> compiler and optimizer are often enemies. For example, overwriting a
> buffer with zeroes might be optimized out when the buffer is not
> accessed again.

I know this is OT, but shouldn't the buffer be filled with random data 
instead of zeros if it's used for storing encrypted data (to make it harder 
to determine the real length of the encrypted data in case it doesn't fill 
the buffer completely)?

Bye...

	Dirk
-- 
Dirk Heinrichs <dirk.heinrichs@altum.de>
Tel: +49 (0)2471 209385 | Mobil: +49 (0)176 34473913
GPG Public Key CB614542 | Jabber: dirk.heinrichs@altum.de
Tox: heini@toxme.se
Sichere Internetkommunikation: http://www.retroshare.org
Privacy Handbuch: https://www.privacy-handbuch.de

Re: Should Ada runtime provide special primitives for cryptography?

[Georg Bauhaus]

On 01.10.14 10:42, Natasha Kerensikova wrote:
> I believe it would not be difficult for a compiler vendor to provide, as
> part of the runtime, a zeroing procedure guaranteed to not be optimized
> away

Have you tried the Volatile aspect?

Re: Should Ada runtime provide special primitives for cryptography?

[Randy Brukardt]

"Georg Bauhaus" <bauhaus@futureapps.invalid> wrote in message 
news:m0gh90$abp$1@dont-email.me...
> On 01.10.14 10:42, Natasha Kerensikova wrote:
>> I believe it would not be difficult for a compiler vendor to provide, as
>> part of the runtime, a zeroing procedure guaranteed to not be optimized
>> away
>
> Have you tried the Volatile aspect?

Right, Volatile provides the guarentees that are needed. In particular, 
C.6(20) says that loads and stores of volatile objects can't be optimized, 
and C.6(22/2) strongly suggests that the loads and stores are exactly of the 
object and nothing else.

So there's no need for an AI; the capability has been in Ada since Ada 95.

                                      Randy.

Re: Should Ada runtime provide special primitives for cryptography?

[Dennis Lee Bieber]

On Wed, 1 Oct 2014 08:42:17 +0000 (UTC), Natasha Kerensikova
<lithiumcat@instinctive.eu> declaimed the following:

>However, when actually implementing cryptographic stuff, cleverness from
>compiler and optimizer are often enemies. For example, overwriting a
>buffer with zeroes might be optimized out when the buffer is not
>accessed again.
>
	Cryptographic "zeroing" does not fill a buffer with 0x00 values. One
approved method is to:

generate random sequence (in a second buffer as you'll need it again)
copy random sequence into crypto buffer
compare buffers to ensure data was changed
invert the bits of the random sequence
copy random sequence into crypto buffer
compare to ensure all data changed
generate second random sequence
copy second sequence into buffer
compare buffers

The first two copy operations ensure every bit in the buffer has been
toggled to both states -- the compares ensure you don't have a "sticky
bit".
-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

Re: Should Ada runtime provide special primitives for cryptography?

[Brad Moore]

On 14-10-01 07:22 AM, Dennis Lee Bieber wrote:
> On Wed, 1 Oct 2014 08:42:17 +0000 (UTC), Natasha Kerensikova
> <lithiumcat@instinctive.eu> declaimed the following:
>
>> However, when actually implementing cryptographic stuff, cleverness from
>> compiler and optimizer are often enemies. For example, overwriting a
>> buffer with zeroes might be optimized out when the buffer is not
>> accessed again.
>>
> 	Cryptographic "zeroing" does not fill a buffer with 0x00 values. One
> approved method is to:
>
> generate random sequence (in a second buffer as you'll need it again)
> copy random sequence into crypto buffer
> compare buffers to ensure data was changed
> invert the bits of the random sequence
> copy random sequence into crypto buffer
> compare to ensure all data changed
> generate second random sequence
> copy second sequence into buffer
> compare buffers
>
> The first two copy operations ensure every bit in the buffer has been
> toggled to both states -- the compares ensure you don't have a "sticky
> bit".

>

Zeroizing can be useful as well. For example, a system might zeroize its 
data to ensure critical, possibly encrypted data cannot be accessed 
after the data has been processed, or before exposing the data to an 
environment where it could be accessed.

Re: Should Ada runtime provide special primitives for cryptography?

[Dennis Lee Bieber]

On Wed, 01 Oct 2014 09:15:02 -0600, Brad Moore <brad.moore@shaw.ca>
declaimed the following:

>On 14-10-01 07:22 AM, Dennis Lee Bieber wrote:
>> On Wed, 1 Oct 2014 08:42:17 +0000 (UTC), Natasha Kerensikova
>> <lithiumcat@instinctive.eu> declaimed the following:
>>
>>> However, when actually implementing cryptographic stuff, cleverness from
>>> compiler and optimizer are often enemies. For example, overwriting a
>>> buffer with zeroes might be optimized out when the buffer is not
>>> accessed again.
>>>
>> 	Cryptographic "zeroing" does not fill a buffer with 0x00 values. One
>> approved method is to:
>>
>> generate random sequence (in a second buffer as you'll need it again)
>> copy random sequence into crypto buffer
>> compare buffers to ensure data was changed
>> invert the bits of the random sequence
>> copy random sequence into crypto buffer
>> compare to ensure all data changed
>> generate second random sequence
>> copy second sequence into buffer
>> compare buffers
>>
>> The first two copy operations ensure every bit in the buffer has been
>> toggled to both states -- the compares ensure you don't have a "sticky
>> bit".
>
>>
>
>Zeroizing can be useful as well. For example, a system might zeroize its 
>data to ensure critical, possibly encrypted data cannot be accessed 
>after the data has been processed, or before exposing the data to an 
>environment where it could be accessed.

	The problem is that, in a really paranoid environment, just writing
zeroes is NOT considered sufficient; there may be subtle traces that
special hardware could pull out. Especially if the data ever hit magnetic
media -- a single write of zeroes on a drive platter, say, may only flatten
the previous data enough that the drive reports it as zeroes, but passing
the head signal to an oscilloscope (for example) might still show ripples
of underlying residual magnetism. The three pass scheme I described ensures
at least two state changes are imposed on those residuals, along with
leaving a random mess as the third pass.

http://csrc.nist.gov/publications/drafts/800-88-rev1/sp800_88_r1_draft.pdf


	Okay -- I'm apparently working from decade old practice (2001 was about
the time I had to be concerned with clearing encryption keys from a laptop
used to load keys into a PPS-rated GPS receiver).

http://cascadeam.typepad.com/it_asset_retirement_value/2012/10/debunking-the-3-pass-overwrite-requirement.html

	OTOH: if the data hits a flash memory device -- grinding up the memory
is the only approved method, since the device may do "wear leveling" which
means the attempt to overwrite the data actually gets written to some other
location on the device (to equalize writes to the media).

-- 
	Wulfraed                 Dennis Lee Bieber         AF6VN
    wlfraed@ix.netcom.com    HTTP://wlfraed.home.netcom.com/

Re: Should Ada runtime provide special primitives for cryptography?

[Florian Weimer]

* Natasha Kerensikova:

> However, when actually implementing cryptographic stuff, cleverness from
> compiler and optimizer are often enemies. For example, overwriting a
> buffer with zeroes might be optimized out when the buffer is not
> accessed again.

Pragma Inspection_Point covers this.

> I believe it would not be difficult for a compiler vendor to provide, as
> part of the runtime, a zeroing procedure guaranteed to not be optimized
> away, a (generic) array comparison guaranteed to execute in a constant
> number of operations and/or branches, etc. And such subprograms would be
> difficult to write externally, and the guarantees difficult to make
> without tight compiler integration.

The compiler cannot guarantee constant-time execution, that's a
property that emerges from the combination of the object code and the
execution environment (or not).