Month: March 2016

AES Pipeline

AES divides the input into chunks of 128 bits. 128 bits is 16 bytes. 16 bytes can be arranged in a 4×4 matrix and are represented in this two dimensional form by AES. This matrix is called the “state”.

Using cryptol, the AES algorithm is described with the following functions

AESRound : (RoundKey, State) -> State

AESRound (rk, s) = AddRoundKey (rk, MixColumns (ShiftRows (SubBytes s)))

The final round leaves out the MixColumns transform.

AESFinalRound : (RoundKey, State) -> State
AESFinalRound (rk, s) = AddRoundKey (rk, ShiftRows (SubBytes s))

The inverse transform is as follows

AESInvRound : (RoundKey, State) -> State

AESInvRound (rk, s) =
InvMixColumns (AddRoundKey (rk, InvSubBytes (InvShiftRows s)))

AESFinalInvRound : (RoundKey, State) -> State

AESFinalInvRound (rk, s) = AddRoundKey (rk, InvSubBytes (InvShiftRows s))

ASN1 Types

ASN1 is a data interoperability format that is widely used in directory, security and network management systems. Data is stored in triplets of TLV – type, length, value (in BER, DER encoding rules). TLV allows a format that is efficient, recursive and self-describing.

The type system is the interesting aspect. A “type” is a descriptor for the data, that the TLV triplet holds. The “type” is stored as a sequence of one or more bytes. This sequence can be as small  as a single byte or be as large as needed (unlimited length). In case of a single byte “type”, the bits 7,8 represent the class of the type (4 classes exist), bit 6 represents whether type is single atomic data element or nested, and bits 5-1 encode the tag of the type.  This single byte type can hold tags from 0 to 30. If the type is outside this range 0-30, the 5 to 1 bits are set to 1, and the actual tag starts in the following bytes of the now multi-byte type. In case of multi-byte “types”, the most significant bit of each byte must be 1, except for the last byte, which must be 0.

There are atomic types and component types.

Atomic types include OBJECT IDENTIFIER types and various strings (bits, ascii, octet), integers, null .

Component types include the ordered SEQUENCE and the unordered SET, both of which types can contain one or more occurrences of different types of data. SEQUENCE OF and SET OF are component types which contain zero or more occurrences of the same types of data.

There is potential for ambiguity as to whether an Object Identifier (OID) in the tagged notation is described as a multi-byte type since the OID is itself multi-byte. It is not, it is described as a single byte ASN1 type with tag = 06 as described in the tag table here and clarified by this Microsoft example of an OID encoding. So the OID value sits in the value field of the TLV triplet, not in the type.

An example of the encoding for RSA private key in PKCS#1 is here. allows lookup of Object Identifiers. Here is a tree display for RSA private key which has OID 1.2.840.113549.1.1.1 –

What are examples of multi-byte ASN1 types ?  The EMV format used in payments and smartcards use two-byte types.

The “abstract” in the name came from a contrast to “transfer syntax notation” which is the on-wire format. The “abstract syntax” maps to “transfer syntax” via encoding rules.

For comparison, consider the XDR scheme used in SunRPC. Here the types (metadata) are not included within the protocol as tags, but defined externally in a .x file which is an input to an rpcgen compiler. Protobuf and capnproto also use external medata in a .proto file. ASN1 now supports Packed Encoding Rules (PER) which remove the tag information for greater compactness and efficiency.  Finally, while ASN1 continues to be used for highly structured information, the rapid growth of JSON/REST protocols in the identity space has been interesting.

The ‘DROWN’ attack on SSL and its extension to QUIC

The DROWN attack was recently shown to cause HTTPS sites supporting SSLv2 to be vulnerable to MITM attacks. An attack extension to QUIC is discussed in section 7 of their paper, along the same lines referenced earlier, which makes it relevant to current discussions of TLS.

Some background. Consider a simple encryption scheme that encrypts a message M to a ciphertext C. Should it always encrypt M to C ? One might think yes. But if yes, then an attacker could create his own extensive tables of encryptions of messages (Mi->Ci) , and then lookup the encrypted (intercepted) message Ci and infer what Mi was. Second, even if there is not a lookup hit, then the maps so collected could be used to deterministically modify Ci, to match another valid Mi.  This latter property is called malleability of encryption. Malleability may be desirable in some cases (homomorphic encryption), but in general it weakens encryption.

So determinism is bad and we want to make the encryption non-deterministic. We can do so by adding some random bytes to beginning of the message every time we encrypt. After decryption, we remove those random bytes and get back our message. These random bytes are called an initialization vector, or also called ‘padding‘.

The way padding is added, is important. If the attacker is able to infer that certain messages do not decrypt to the expected padding format (via error messages returned from the server), then he can narrow the range of valid messages. A ‘padding oracle’ is a server that freely answers whether an encrypted message is correctly padded or not. This is the basis of the Bleichenbacher attack.

The SSLv2 servers are using an old form of the RSA which is unpadded, deterministic and malleable. This property is the basis of many attacks, that involve a protocol downgrade (e.g. a PFS cipher to RSA cipher, or TLS to SSL) , or attack a known weak protocol. The Breach attack used the fact that compression changed the size of a message in a predictable way to infer bytes of a key. Compression is disabled in TLS1.2.

But why should this attack be possible with newer protocols like QUIC ? QUIC does not even support PKCS#1 v1.5 encryption.

QUIC achieves low latency by caching TLS state on the client. If any part of the protocol is using a deterministic behaviour it can be exploited. The Jager paper makes the following observations. 1. The server authentication is performed only in the connect phase, not in the repeat phase.  and 2. The signed SCFG message is made independent of the client request, which makes it possible for the server or an attacker to precompute it. So, there is exploitable determinism.

Certain fixes have been proposed in QUIC v31, to switch the server signature from a static signature of the server config to a signature of the server config with a hash of the client hello message. This is claimed to eliminate the DROWN vulnerability.

Erlang ‘for’ and ‘if’

When thinking of immutable state, I imagine a large


box being broken into a chain of multiple smaller mini-boxes,

input0->[pbox0]->output0 -> [pbox1]->output1 ->[pbox2]->output3

with each individual box accomplishing a change in its input to its output, without keeping any internal mutable state.

Which reminds me of Linear-Time-Invariant systems. As long as each part of the system is linear and time-invariant, a large system can be composed of simpler parts and still be analyzed by deriving a composite transfer function. The composite system can be studied for its stability and loss/gain characteristics and adjustments made in the system design.

I suspect a similar payoff occurs with functional programming. But it is not so clearly stated or visible in the ability to analyze large programs. Erlang is essentially a version of event driven programming. The conciseness of expression is encouraging, but I hope to arrive at good examples of program composition.

Meanwhile the ‘if’ statement in erlang is a curveball. In addition to the odd syntax, and statements like true->false, one finds one cannot place a log statement anywhere inside a set of statements to see what’s going on. Punctuation rules. The trick is to place the log a comma before the last expression before the semicolon.

   Val >= Left andalso Val =< Right ->
   io:format("==> ok~p<~p<~p\n\n",[Left,Val,Right]),

   true ->
   io:format("==>not ok ~p<~p<~p\n\n",[Left,Val,Right]),

The semicolons indicate different phrases which are pattern-matching options. The commas are continued statements within the same phrase. The last statement in the phrase is the return value. The last phrase is typically a catch-all, in this case returning a value of false. The case statement is more commonly used than the if. The -> denotes  ‘lhs condition is mapped to rhs’ .  

The ‘for’ statement does not exist at all and below are alternatives.

foreach(Fun, List)->ok, %% just applies a function Fun to each element of a list
foldl(Fun, Accumulator, List)-> Acc1,  %% fold list left to right into an accumulator
foldl(Fun, Accumulator, List)-> Acc1 %% fold list right to left into an accumulator
map(Fun, List1) -> List2  %% maps a list to a new list

The = sign in erlang is used for (a) immutable assignment of a term to a value and (b) for comparing if a previously assigned term or expression of terms is the same as another term or value – this is called pattern matching. One cannot reassign a term to a new value, so the math notion of equality always holds. The = used in C/Java could be called mutable assignment, every variable is hiding within it mutable state. A term in erlang does have an internal state of bound or unbound. On a successful pattern match any unbound variable becomes bound.

1> [H|T] = [1,2,3].

2> io:write(H) .

To generate a list of numbers, like range(n) in python, there is lists:seq(1,n). io:fwrite(“~p”, [lists:seq(1,20)]).

The philosophy behind some of these decisions is discussed here An objective is to make it impossible to write runaway loops – to make the runtime system always be able to recover and reallocate its cycles. A related aspect is to let-it-fail and not write a lot of exception handling, defensive code.