Bash script to convert NIST vectors to debug scripts

Question

TL;DR: The Bash script converts a published, somewhat-structured text file into a format usable by my testing infrastructure. It's slow, I think it's ugly -- although it is fully functional.

---

The NIST provides test vectors for verifying the correct operation of a Galois Counter Mode (GCM) when used with the AES block cipher (I only care about the 128-bit key files, and have not looked into the format of the other files).

In order to actually use these test vectors for automated testing of my GCM-AES implementation, I have to convert them from the RSP file that they come in, into a debug script that my chip simulator (mspdebug) can use. There are also other scripts, as well as driver code, that the test vectors ultimately interact with -- but it is sufficient for this problem to have each variable in the RSP file set in memory with an mw command (e.g., "PT = 010203" should become "mw PT 0x01 0x02 0x03"), so long as each group of tests that share common values is broken into a separate file.

As an operational example, from this section of the gcmEncryptExtIV128.rsp input file, this output is generated. Note that the input file generates 525 such files, from 525 corresponding sections within itself. The script, as written, will not work on just the subsection linked above, as the complete RSP has some extra junk at the start that gets trimmed out (though you can probably get it to work with some fiddling). Note also that none of the encryption tests are marked with a "FAIL" -- this token occurs only within the decryption tests, but the contents of the two RSP files are otherwise identical. For the sake of uniformity, each encryption test (as well as the non-failing decryption tests) have an output line of mw FAIL 0.

The script is incredibly slow (it takes ~15 minutes to run against a single RSP file on a modest modern machine), primarily because of the sed expression for ensuring that every test block has a FAIL setting. It does, however, correctly spit out each test group into a well-named file, and convert all of the input data into a format that my simulator can handle.

Any thoughts on how to speed this up, improve the readability, or conform to best practices are welcome. More drastic actions (e.g., re-casting this as an AWK script) are also interesting to me, if folks think this approach is just all-out incorrect.

#!/bin/bash

if ! [ -f "$1" ]; then
  echo "You must specify a valid input file."
  exit
fi

# Strip off the file extension of the input file name
BASEFILE=${1%.*}

# Strip off any trailing digits of the input file name
until [ "$TEMP" == "$BASEFILE" ]; do
  TEMP="$BASEFILE"
  BASEFILE="${BASEFILE%[0-9]}"
done

unset TEMP

# - Convert the file's line endings
# - Strip out the RSP file header and leading blank lines
dos2unix < "$1" | tail -n +7 > temp.txt

# Convert the "len" values from decimal to hex
# Process the temp file line by line to do this
cat temp.txt | \
while read VARNAME EQUALS VALUE; do
  # If this line's variable name ends in "len"
  if [ "${VARNAME%%*len}" != "$VARNAME" ]; then
    # Output the line (removing the starting "[", up to the = sign
    echo -n ${VARNAME#[[]} $EQUALS" "
    # Then convert the value from decimal to hex, printing it at the very end of the line.
    # s/^(.?.)$/0x\1 0x0/ - If we have a 1 or 2 digit number, put it in the LSB position.
    # s/^(.?.)(..)$/0x\2 0x\1/ - If we have a 3 or 4 digit number, put it in little-endian order.
    echo "obase=16; ${VALUE%%[]]*}" | bc | sed -re 's/^(.?.)$/0x\1 0x0/' -e 's/^(.?.)(..)$/0x\2 0x\1/'
  else
    # This isn't a length variable? It's already hex, then; just print it straight out.
    echo $VARNAME $EQUALS $VALUE;
  fi
done > temp2.txt

mv temp2.txt temp.txt

# - Strip out the block-level variable's enclosing square brackets
# - Strip out the "Count" lines (we don't need them for anything).
# - Strip lines with no values
# - Strip trailing spaces
sed -ri -e 's/\[|\]//g' -e '/^Count .*/d' -e '/^[^ ]+ = $/d' -e 's/ +$//' temp.txt

# Convert the "var = value" format to "mw var value" used by MSPD
sed -rie 's/^([^ ]*) =/mw \1/' temp.txt

# Convert hex values to 0x## byte notation MSPD will understand.
# :loop                             - A label we'll need later
# ^(mw (Key|IV|PT|AAD|CT|Tag) )     - Match only these keys (and eat them and their trailing space)
# ((0x[0-9a-f]{2} )*)               - Eat up any parts of the hex string that have already been split into 0x-prefixed bytes
# ([0-9a-f]{2})                     - Capture the next un-processed byte's worth of digits, if they exist
# (.*)$                             - Capture the rest of the line.
# \1\30x\5 \6                       - Paste the key (and its space), the processed hex, the new 0x, hex byte, and space, and then any remainder.
# t loop                            - If we actually replaced something, run the replace again (go back to :loop)
sed -ri -e ':loop' -e 's/^(mw (Key|IV|PT|AAD|CT|Tag) )((0x[0-9a-f]{2} )*)([0-9a-f]{2})(.*)$/\1\30x\5 \6/' -e 't loop' temp.txt

# Split each test block into its own file.
# /^mw Keylen/                      - If this is a "Keylen" line, it's the start of a new test block
# {x="test-"++i;}                   - Increment our counter (start printing to a new file)
# {print > x;}                      - Append the current line in the buffer to the current file.
awk '/^mw Keylen/{x="test-"++i;}{print > x;}' temp.txt

# - Normalize each test so it has an appropriate FAIL line
# - Normalize each test so it reads the test round (after setting variables)
# - Rename the files to reflect the tests they contain.
for FILE in test-*; do
  # Make sure that there always exists a pass OR fail indicator for each test round.
  # --- This is incredibly slow :( ---
  # $!P - If this is not the last buffer, print it.
  # 7~1N - Process 2 lines, starting from the 7th line on
  # /FAIL\n$/! - If this is NOT a FAIL line followed by a blank line...
  # s/(.*)\n$/ - If this IS (then) a line followed by a blank line...
  # /\1\nmw FAIL 0\n/ - insert "md FAIL 0" as a line.
  # D - shift out the oldest (first) line, and jump back to the N
  sed -ri -e '$!P' -e '7~1N' -e '/FAIL\n$/!{s/(.*)\n$/\1\nmw FAIL 0\n/}' -e 'D' "$FILE"

  # Replace all the "FAIL" lines with appropriate memory sets.
  sed -rie 's/^FAIL$/mw FAIL 1/' "$FILE"

  # For each discrete set of test variables, read in the file responsible for actually running a single test round.
  # 7~1 - Skip the first 7 lines of the file
  # s/^$/ - If this is a blank line...
  # /read gcm_test_round.mspd\n/ - Insert the appropriate read line.
  sed -rie '7~1s/^$/read gcm_test_round.mspd\n/' "$FILE"

  # Rename the files to reflect the class of tests they contain.
  # head -n5 "$FILE" - Grab the first five lines of the file, which hold (in order) the values for key length, IV length, text length, AAD length, and tag length for all the test entries contained in that file.
  # ^.* 0x(.?.) 0x(.?.) - Match the two 1-2 digit hex numbers at the end of the lines
  # ibase=16; \2\1 - Put the bytes back into big-endian, and strip the 0x (prep for BC)
  # { while read; do echo $REPLY | bc; done; } - Pipe each line to BC one by one, converting the hex values back to decimal
  # :a - Label "a"
  # N - Append another line to the buffer
  # $!ba - If this is NOT the last line, branch to A
  # s/\n/-/g - Replace all the newlines in the processing space with dashes
  mv "$FILE" "$BASEFILE"`head -n5 "$FILE" | sed -re 's/^.* 0x(.?.) 0x(.?.)/ibase=16; \2\1/g' | { while read; do echo $REPLY | bc; done; } | sed -re ':a' -e 'N' -e '$!ba' -e 's/\n/-/g'`.mspd

  # The resulting renamed files are of the format:
  # [BASEFILE][Keylen]-[IVlen]-[PTlen]-[AADlen]-[Taglen].mspd

  # Get rid of the temporary file
  rm "${FILE}e"
done

# Get rid of temporary files
rm temp.txt{,e}

Answer 1

Rewriting it in AWK would definitely result in a huge improvement, enough to say that writing it in Bash was a poor choice. Many of the considerations for this problem favour AWK:

• The input is line-oriented.
• Nearly every line has the same key = value format, except for the headers with [key = value] instead. Most importantly, they all share the same = delimiter.
• All of the processing can be done using simple text transformations and arithmetic.
• Processing can be done in one pass, with very little state to maintain.

I think that Bash is underpowered for this problem, and is therefore a poor fit. The repeated use of sed is not only a performance barrier; the constant intermingling of Bash and sed hurts readability.

Of course, any other general-purpose programming language would also work. However, considering that any system that has Bash will also have AWK, and AWK is just powerful enough to handle this problem comfortably, that's what I would choose. Besides, you already used a tiny bit of AWK within your Bash script — why not go all the way? ☺

The AWK program below is much faster than your Bash script, and in my opinion, more readable. That said, there are some minor improvements that could be made to the Bash-based solution. I may eventually return to review it.

#!/usr/bin/awk -f

BEGIN {
    FS = " = ";
    NUM_HEADERS = 0;
}

######################################################################
# Skip first 6 lines
######################################################################
FNR < 7 { next }

######################################################################
# dos2unix
######################################################################
{ sub("\r$", ""); }

######################################################################
# Read headers, of the form
# [Keylen = 96]
######################################################################
/\[.*\]/ {
    gsub("\\[|\\]", "");
    HEADER_NAME[NUM_HEADERS++] = $1;
    HEADER_VALUE[$1] = $2;
    next;
}

######################################################################
# End of headers.  Determine output file, and write out the headers.
# Output filename is of the form
# [BASEFILE][Keylen]-[IVlen]-[PTlen]-[AADlen]-[Taglen].mspd
######################################################################
NUM_HEADERS > 0 {
    if (OUT) {
        end_of_stanza();
        close(OUT);
    }
    basename = FILENAME;
    sub("\\..*", "", basename);
    sub("[0-9]*$", "", basename);
    OUT = sprintf("%s%d-%d-%d-%d-%d.mspd",
                  basename,
                  HEADER_VALUE["Keylen"],
                  HEADER_VALUE["IVlen"],
                  HEADER_VALUE["PTlen"],
                  HEADER_VALUE["AADlen"],
                  HEADER_VALUE["Taglen"]);

    for (h = 0; h < NUM_HEADERS; h++) {
        header_name = HEADER_NAME[h];
        hex_value = sprintf("%04x", HEADER_VALUE[header_name]);
        printf "mw %s 0x%s 0x%s\n", header_name, substr(hex_value, 3, 2), substr(hex_value, 1, 2) > OUT;
    }
    NUM_HEADERS = 0;
    FAIL = "";
    next;
}

######################################################################
# Split values of Key, IV, PT, AAD, CT, and Tag into hex bytes
######################################################################
$1 ~ /^(Key|IV|PT|AAD|CT|Tag)$/ && $2 ~ /^([0-9a-f][0-9a-f])+$/{
    split($2, a, "");
    $2 = "";
    for (i = 1; i < length(a); i += 2) {
        $2 = sprintf("%s 0x%s%s", $2, a[i], a[i + 1]);
    }
    $2 = substr($2, 2);
}

######################################################################
# Stanza processing: mark failure or non-failure
######################################################################
function end_of_stanza() {
    if (FAIL != "") {
        print "mw FAIL", FAIL > OUT;
        print "read gcm_test_round.mspd\n" > OUT;
    }
    FAIL = "0";
    print "" > OUT;
}

$1 == "FAIL" {
    FAIL = "1";
    next;
}
$1 == "Count" {
    end_of_stanza();
    next;
}
END {
    end_of_stanza();
    close(OUT);
}

######################################################################
# Normal body line
######################################################################
!/^$/ {
    if ($2 == "") {
        print "mw", $1 > OUT;
    } else {
        print "mw", $1, $2 > OUT;
    }
}