david wong

Hey! I'm David, cofounder of zkSecurity and the author of the Real-World Cryptography book. I was previously a crypto architect at O(1) Labs (working on the Mina cryptocurrency), before that I was the security lead for Diem (formerly Libra) at Novi (Facebook), and a security consultant for the Cryptography Services of NCC Group. This is my blog about cryptography and security and other related topics that I find interesting.

StrobeGo posted May 2017

I wrote an opinionated and readable implementation of the Strobe Protocol Framework in Go here.

It hasn't been thoroughly tested, and its main goal was to help me understand the specification of Strobe while kicking around ideas to challenge the spec.

It started a discussion on the mailing list if you're interested.

I hope that this implementation can help someone else understand the paper/spec better. The plan is to have a usable implementation by the time Strobe's specification is more stable (not that it isn't, its version is actually 1.0.2 at the moment).

Following is a list of divergence from the current specification:

Operate

The main Operate public function that allows you to interact with STROBE as a developer has a different API. In pseudo code:

Operate(meta bool, operation string, data []byte, length int, more bool) → (data []byte)

I've also written high level functions to call the different known operations like KEY, PRF, send_ENC, etc... One example:

// `meta` is appropriate for checking the integrity of framing data. 
func (s *strobe) send_MAC(meta bool, output_length int) []byte {
  return s.Operate(meta, "send_MAC", []byte{}, output_length, false)
}

The meta boolean variable is used to indicate if the operation is a META operation.

// operation is meta?
if meta {
    flags.add("M")
}

What is a META operation? From the specification:

For any operation, there is a corresponding "meta" variant. The meta operation works exactly the same way as the ordinary operation. The two are distinguished only in an "M" bit that is hashed into the protocol transcript for the meta operations. This is used to prevent ambiguity in protocol transcripts. This specification describes uses for certain meta operations. The others are still legal, but their use is not recommended. The usage of the meta flag is described below in Section 6.3.

Each operation that has a relevant META variant, also contains explanation on it. For example the ENC section:

send_meta_ENC and recv_meta_ENC are used for encrypted framing data.

The operations are called via their strings equivalent instead of their flag value in byte. This could in theory be irrelevant if only the high level functions were made available to the developers.

A length argument is also available for operations like PRF, send_MAC and RATCHET that require a length. A non-zero length will create a zero buffer of the required length, which is not optimal for the RATCHET operation.

// does the operation requires a length?
if operation == "PRF" || operation == "send_MAC" || operation == "RATCHET" {
    if length == 0 {
      panic("A length should be set for this operation.")
    }

    // create an empty data slice of the relevant size
    data = bytes.Repeat([]byte{0}, length)

} else {
    if length != 0 {
      panic("Output length must be zero except for PRF, send_MAC and RATCHET operations.")
    }

    // copy the data not to modify the original data
    data = make([]byte, len(data_))
    copy(data, data_)
}

Verbose

One of my grip with the Strobe's specification is that nothing is truly explained through words: the reader is expected to follow reference snippets of code written in Python. Everything has been optimized and it is quite hard to understand what is really happening (hence why I wrote this implementation in the first place). To remediate this, I wrote a clear path of what is happening for each operation. It is great for other readers who want to understand what is happening, but obviously not the optimal thing to do for an efficient implementation :)

It looks like a bunch of if and else if (Go does not have support for switch):

if operation == "AD" { // A
    // nothing happens
} else if operation == "KEY" { // AC
    cbefore = true
    forceF = true
} else if operation == "PRF" { // IAC
    cbefore = true
    forceF = true
    ...

_Duplex

I have omited any function name starting with _ as Go has a different way of making functions available out of a package: make the first letter upper case.

The _duplex function was written after Golang's official SHA-3 implementation and is not optimal. The reason is that SHA-3 does not need to XOR anything in the state until after either the end of the rate (block size) or the end of the input has been reached. Because of this, Go's SHA-3 implementation waits for these to happen while STROBE often cannot: STROBE often needs the result right away. This led to a few oddities.

pos

I do not use the pos variable as it is easily obtainable from the buffered state. This is another (good) consequence of Go's decision on waiting before running the Keccak function. Some other implementations might want to keep track of it.

cur_flags

The specification states that cur_flags should be initialized to None. Which is annoying to program (see how I did it for I0). This is why I took the decision that a flag cannot be zero, and I'm initializing cur_flags to zero.

I'm later asserting that the flag is valid, according to a list of valid flags

// operation is valid?
var flags flag
var ok bool
if flags, ok = OperationMap[operation]; !ok {
    panic("not a valid operation")
}

R is always R

The specification states that the initialization should be done with R = R + 2. This is to have a match with cSHAKE's padding when using some STROBE instances like Strobe-128/1600 and Strobe-256/1600.

I like having constants and not modifying them. So I initialize with a smaller rate (block_size) and do not conform with cSHAKE's specification. Is it important? I think yes. It does not make sense to use cSHAKE's padding on Strobe-128/800, Strobe-256/800 and Strobe-128/400 as their rate is smaller than cSHAKE's defined rate in its padding.

EDIT: I ended up reverting this change. As I only implemented Strobe-256/1600, it is easy to conform to cSHAKE by just initializing with R + 2 which will not modify the constant R.

Well done! You've reached the end of my post. Now you can leave a comment or read something else.

Comments

matt

Please learn to use gofmt :) Your Go code looks terribly formatted.
I suggest using a plugin for your editor (e.g. GoSublime for Sublime Text, go-plus for Atom) which does that job automatically.

david

just did and got that sublime text plugin, thanks matt!

matt

Anyhow, awesome work! I really enjoy your blog. Thank you! :)

leave a comment...