Size of textual version

  • New Wordpress Plug-In Forum
    Guest:

    Just a note that we have a new forum to contain discussions relating to the Wordpress plug-in which Daniel Persson originated and has been making great progress on. You'll find it under "Server-Side Solutions."

    /Steve.

kalaspuffar

Well-known member
May 19, 2018
269
91
Sweden
coderinsights.com
Hi @sengsational

I'm not really sure what you are printing there because nothing is loaded. Looked at the show identity and that activity loads the identity. So both print and save identity after creation is a bit random I'm afraid.

So at the moment to get a good identity you show identity before print or saving.

Great catch. Create an issue and I will fix this asap.

Best regards
Daniel
 

Steve

Administrator
Staff member
May 6, 2018
992
290
www.grc.com
@kalaspuffar :
The way it works (my idea! Just bragging ;)) is that the other 19 characters of the line, plus the line number (IIRC, one byte 0-based appended to the end; Steve's addition) are fed through SHA256, and the result is modded with 56 to get the check char.
Shane's right. The textual identity import/export system in my client (and this is part of the SQRL standard spec for cross-client compatibility) has a check character at the end of every line. As I recall, the lines are independent of each other, but during input the client won't let the user start on the next line if the one above is not green.

This is not documented anywhere yet, but my Intel assembly code implementation is here:

203

And here's the "HashBufferMod56" routine:

204
 

kalaspuffar

Well-known member
May 19, 2018
269
91
Sweden
coderinsights.com
As I suspected, if I forced a storage.read() before the textual version was printed, it printed the right thing. I'm not sure exactly where the best place (in the code) would be to do this forced read, or if, rather than force a read, the exact problem with the state of SQRLStorage at the time of first identity creation can be identified. But to be sure, when I forced read before the text was created, it created the right length of output. Here's the quick and dirty way I "fixed" it:
Sorry, totally missed the meaning of this message, probably because it was hard to decipher on my phone yesterday, didn't see the image.

You are right, adding a load would probably solve this issue. And I suggest to either load it on the NewIdentityDone page before you choose to show, save or print. Or perhaps you may add it to each of the functions so they are tasked to keep the identity information fresh. The positive thing about doing it that way is that they will work independently on the structure of the program, and a load operation is not that time-consuming.

Best regards
Daniel
 

kalaspuffar

Well-known member
May 19, 2018
269
91
Sweden
coderinsights.com
Hi @Steve

I'm not seeing that we do that much different. But Shanes comment about adding an extra byte of a checksum for the whole text would make sense but I still don't get why we usually get the same result on our identity outputs but when the outputs get large enough we differ on the last bytes. If you added extra information we would have differences on every identity. You would always add a byte that I didn't expect but that is not the case. It just differs if we long identities.

p != t2

:(
 

PHolder

Well-known member
May 19, 2018
918
124
Picture of code
hey Daniel I don't want to be too pedantic (I get that English is not your first language), but I wanted to note your variable should be called "remainder" not "reminder". (Which isn't any bug or anything but is relevant if someone were searching your code for such a thing.) (At least I assume that, because it's the result of a MOD operation... but I may be completely confused about its purpose, and you mean "check digit".)
 

PHolder

Well-known member
May 19, 2018
918
124
This is not documented anywhere yet, but my Intel assembly code implementation is here
Any chance you can make a couple of samples readily available... test vectors as it were. Maybe something short, medium and longer?

So it might look like:
0000: 01 02 03 04 05 06 07 08

Is encoded as:
abcd efgh ijkl mnop
 

kalaspuffar

Well-known member
May 19, 2018
269
91
Sweden
coderinsights.com
hey Daniel I don't want to be too pedantic (I get that English is not your first language), but I wanted to note your variable should be called "remainder" not "reminder". (Which isn't any bug or anything but is relevant if someone were searching your code for such a thing.) (At least I assume that, because it's the result of a MOD operation... but I may be completely confused about its purpose, and you mean "check digit".)
Code:
commit 3ba02eaa6961b2b4581b936a8bdcff0447771e83 (HEAD -> master, origin/master, origin/HEAD)
Author: Daniel Persson
Date:   Fri Mar 15 08:24:07 2019 +0100

    Spell correction.
Thank you! :)
 

PHolder

Well-known member
May 19, 2018
918
124
EDIT: This is NOT correct. I had forgotten to include the line number "check char". :-(

Any chance you can make a couple of samples readily available... test vectors as it were. Maybe something short, medium and longer?

So it might look like:
0000: 01 02 03 04 05 06 07 08

Is encoded as:
abcd efgh ijkl mnop
Always fun replying to yourself.

I just threw together some code, based on my understanding of 2.2.1 of https://github.com/Novators/sqrl-spec/blob/master/draft-sqrl.txt , and generated this output. Hopefully it is correct and someone can confirm it:

Code:
    final byte[] testArray = new byte[] {
      0x01,0x02,0x03,0x04,0x05,0x06,0x07,0x08, 0x09,0x0a,0x0b,0x0c,0x0d,0x0e,0x0f,0x10,
      0x11,0x12,0x13,0x14,0x15,0x16,0x17,0x18, 0x19,0x1a,0x1b,0x1c,0x1d,0x1e,0x1f,0x20,
      0x21,0x22,0x23,0x24,0x25,0x26,0x27,0x28, 0x29,0x2a,0x2b,0x2c,0x2d,0x2e,0x2f,0x30,
      0x31,0x32,0x33,0x34,0x35,0x36,0x37,0x38, 0x39,0x3a,0x3b,0x3c,0x3d,0x3e,0x3f,0x40,
      0x41,0x42,0x43,0x44,0x45,0x46,0x47,0x48, 0x49,0x4a,0x4b,0x4c,0x4d,0x4e,0x4f,0x50
    };
    final String encodeResult[] = Base56Encoder.base56Encode(testArray);
    for (final String s: encodeResult)
    {
      System.out.println(s);
    }
    final byte[] decodeResult = Base56Decoder.base56Decode(encodeResult);
    assertIdenticalArrays(testArray, decodeResult);

which produces this output:

0000: 01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10
0010: 11 12 13 14 15 16 17 18 19 1A 1B 1C 1D 1E 1F 20
0020: 21 22 23 24 25 26 27 28 29 2A 2B 2C 2D 2E 2F 30
0030: 31 32 33 34 35 36 37 38 39 3A 3B 3C 3D 3E 3F 40
0040: 41 42 43 44 45 46 47 48 49 4A 4B 4C 4D 4E 4F 50

b6w8 RYMv S427 Gtt5 sXBF
UB5n vHZH PbHr uAM9 MgUt
fzT8 qs8f EEEp kUPV GH6h
ac4u Zdrk CwLJ Wxmy 8upt
rU9N Bn6P qcY9 HXKt ybER
Sdh9 R22r SjAd 48i2 Y
 
Last edited:

PHolder

Well-known member
May 19, 2018
918
124
EDIT: I still think the padding might be a problem, but my check chars are wrong... I wasn't including the line number char.

Hi @Steve

I'm not seeing that we do that much different. But Shanes comment about adding an extra byte of a checksum for the whole text would make sense but I still don't get why we usually get the same result on our identity outputs but when the outputs get large enough we differ on the last bytes. If you added extra information we would have differences on every identity. You would always add a byte that I didn't expect but that is not the case. It just differs if we long identities.

p != t2

:(
Daniel:

I think I might know the reason for your issue:

I think it boils down to step 5 of 2.2.1 of https://github.com/Novators/sqrl-spec/blob/master/draft-sqrl.txt , specifically:
5. Append '2' (character in ALPHABET at position 0) to BASE until BASE is BASE_LENGTH bytes long.
I know this added an extra char to my test output, above. And the fact there is a '2' in your difference seems to point at this as well.

You may actually have a problem with this input: (my output included, assuming I got this thing working right)

0000: 00 00 00 00
2222 22e

And here is another one that initially caused me some grief:

0000: FF FF FF FF
Zeai n9q
 
Last edited:

PHolder

Well-known member
May 19, 2018
918
124
picture of code
Looking at the picture of your code, you're definitely not handling zero padding well... That might be the difference you're seeing. Try encoding and decoding a block of zero bytes as a unit test. If the input and output sizes are not the same, then you still have an issue.

I posted some examples in the newsgroup, that could be used as unit tests, if that is helpful.
 

kalaspuffar

Well-known member
May 19, 2018
269
91
Sweden
coderinsights.com
Hi everyone.

Been a while since anyone wrote something here. I found that the base56 algorithm in Android is correct and will read all textual input from @Steve's client but the textual input created will not be correct if you input it back into the windows client.

This is because I can't figure out how the zero-padding works. The padding is added before a line number so it should be the second to last character in the sequence.

Example: ".....MegiE2t"

2 is the zero-padding and then we have the line number t.

After reading the specification at https://github.com/Novators/sqrl-spec/blob/master/draft-sqrl.txt I implemented the following code to padd:

Code:
// len = the length of base56 encoded text written without line markers.
// paddLen = the length we need to padd the original length to.

// Added extra padding.
int paddLen = (int)Math.ceil( data.length * 8.0 / (Math.log(56) / Math.log(2)));
for(int j = len; j < paddLen; j++) {
    resultStr += (char)BASE56_ENCODE[0];
    md.update(BASE56_ENCODE[0]);
}
Sadly this doesn't work. I added 2 test cases and have an open pull request on Github.


Either I've misunderstood something fundamental or the specification is not correct.

Anyone, have a suggestion?
 

PHolder

Well-known member
May 19, 2018
918
124
Anyone, have a suggestion?
I commented on this some time ago... because I implemented it at that time and then looked at your code as a comparison and found you weren't handling the zero padding according to the spec written by Shane et el. I'll see if I can find my old post, and maybe even my old code and edit this note when I have something more.

This was my previous comment: https://sqrl.grc.com/threads/size-of-textual-version.442/page-2#post-2767

specifically:

I think it boils down to step 5 of 2.2.1 of https://github.com/Novators/sqrl-spec/blob/master/draft-sqrl.txt , specifically:
5. Append '2' (character in ALPHABET at position 0) to BASE until BASE is BASE_LENGTH bytes long.
EDIT: okay, here's my working and tested code, hope it helps:

Code:
import java.math.BigInteger;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import org.apache.commons.lang.ArrayUtils;

final class Common
{
  final static String BASE56_CHAR_STR = "23456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnpqrstuvwxyz";
  final static char[] BASE56_CHARS = BASE56_CHAR_STR.toCharArray();
  final static int BASE_INT = 56;
  final static BigInteger BASE = BigInteger.valueOf(BASE_INT);
  final static int CHARS_PER_LINE = 19;
  final static int charLookup[] = new int[256];
  
  static
  {
    for (int i=0; i<256; i++) charLookup[i]=-1;
    int v = 0;
    for (final char c: BASE56_CHARS)
    {
      charLookup[(int)c] = v++;
    }
  }
  
  static char calculateCheckDigit(final String lineToCalculateCheckDigitOf, final int lineNumber)
  {
    if ((lineNumber <0) || (lineNumber >255))
      throw new IllegalArgumentException("Input line number is not valid (in byte range 0-255): " + lineNumber);

    final MessageDigest md;
    try
    {
      md = MessageDigest.getInstance("SHA-256");
    }
    catch (final NoSuchAlgorithmException e)
    {
      throw new IllegalStateException("Unable to get SHA-256 hash", e);
    }
    md.update(lineToCalculateCheckDigitOf.getBytes());
    final byte[] lineNumberByte = new byte[1];
    lineNumberByte[0] = (byte)lineNumber;
    final byte[] digest = md.digest(lineNumberByte);
    ArrayUtils.reverse(digest);
    final BigInteger val = new BigInteger(1, digest);
    return lookupBase56Char(val.mod(Common.BASE).intValue());
  }

  static char lookupBase56Char(int intValue)
  {
    return Common.BASE56_CHARS[intValue];
  }

  public static BigInteger getDigitFromChar(final char c)
  {
    final int result = charLookup[(int)c];
    if (result <0) throw new IllegalStateException("Invalid input char: " + c);
    return BigInteger.valueOf(result);
  }
}
Code:
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import org.apache.commons.lang.ArrayUtils;

public final class Base56Encoder
{
  public static String[] base56Encode(final byte[] binaryData)
  {
    final int expectedLength = (int) Math.ceil((binaryData.length*8)/(Math.log(Common.BASE_INT)/Math.log(2)));

    final List<String> lines = new ArrayList<>();
    final byte[] bytesConvertedToLittleEndian = binaryData.clone(); 
    ArrayUtils.reverse(bytesConvertedToLittleEndian);
    BigInteger val = new BigInteger(1, bytesConvertedToLittleEndian);
    StringBuffer lineUnderContruction = new StringBuffer();
    int numberOfDigitsOnLine = 0;
    int totalNumberOfDigits = 0;
    int lineNumber = 0;
    while (totalNumberOfDigits < expectedLength)
    {
      if (val.compareTo(BigInteger.ZERO) > 0)
      {
        final BigInteger twoVals[] = val.divideAndRemainder(Common.BASE);
        final int digitLookup = twoVals[1].intValue();
        val=twoVals[0];
        lineUnderContruction.append(Common.lookupBase56Char(digitLookup));
      }
      else
      {
        lineUnderContruction.append(Common.BASE56_CHARS[0]);  // pad with "zero"
      }
      numberOfDigitsOnLine++;
      totalNumberOfDigits++;
      if (numberOfDigitsOnLine >= Common.CHARS_PER_LINE)
      {
        lineUnderContruction.append(Common.calculateCheckDigit(lineUnderContruction.toString(), lineNumber++));
        lines.add(formatLineForHuman(lineUnderContruction.toString()));
        lineUnderContruction = new StringBuffer();
        numberOfDigitsOnLine = 0;
      }
    }
    if (numberOfDigitsOnLine > 0)
    {
      lineUnderContruction.append(Common.calculateCheckDigit(lineUnderContruction.toString(), lineNumber++));
      lines.add(formatLineForHuman(lineUnderContruction.toString()));
    }
    
    return lines.toArray(new String[0]);
  }

  private static String formatLineForHuman(final String inputLine)
  {
    final StringBuffer sb = new StringBuffer();
    int charMod = 0;
    for (final char c : inputLine.toCharArray())
    {
      sb.append(c);
      charMod++;
      if (charMod == 4)
      {
        sb.append(' ');
        charMod = 0;
      }
    }
    return sb.toString();
  }
}
Code:
import java.math.BigInteger;
import org.apache.commons.lang.ArrayUtils;

public final class Base56Decoder
{
  public static byte[] base56Decode(final String[] textInput)
  {
    final StringBuilder inputToBeReversed = new StringBuilder();
    int lineNumber = 0;
    for (final String line : textInput)
    {
      final String valueLine = line.replaceAll("[^"+Common.BASE56_CHAR_STR+"]", "");
      final String checkLine = valueLine.substring(0, valueLine.length()-1);
      final char expectedCheckChar = Common.calculateCheckDigit(checkLine, lineNumber++);
      if (expectedCheckChar != valueLine.charAt(valueLine.length()-1))
      {
        System.out.println("Invalid checksum on line \"" + line + "\" , expected: " + expectedCheckChar);
        return new byte[0];
      }
      inputToBeReversed.append(checkLine);
    }
    final String reversedInput = inputToBeReversed.reverse().toString();
    final int expectedNumberOfBytes = (int)(reversedInput.length()*(Math.log(Common.BASE_INT)/Math.log(2))/8);
    BigInteger val = BigInteger.ZERO;
    for (final char c : reversedInput.toCharArray())
    {
      val = val.multiply(Common.BASE).add(Common.getDigitFromChar(c));
    }
    final byte[] arrayToConvertToBigEndian = val.toByteArray();
    //HexDumper.dumpInHex(arrayToConvertToBigEndian);
    if (arrayToConvertToBigEndian.length < expectedNumberOfBytes)
    {
      //System.out.format("zero padding: expectedNumberOfBytes=%d, arraySize=%d%n", expectedNumberOfBytes, arrayToConvertToBigEndian.length);
      final byte[] result = new byte[expectedNumberOfBytes];
      int i=0;
      for(; i<expectedNumberOfBytes-arrayToConvertToBigEndian.length; i++)
      {
        result[i] = 0;
      }
      for(int j=0; j<arrayToConvertToBigEndian.length; j++)
      {
        result[i++]=arrayToConvertToBigEndian[j];
      }
      ArrayUtils.reverse(result);
      return result;
    }
    else if (arrayToConvertToBigEndian.length > expectedNumberOfBytes)
    {
      //Extra zero byte because of sign in BigInteger
      //System.out.format("sign issue: expectedNumberOfBytes=%d, arraySize=%d%n", expectedNumberOfBytes, arrayToConvertToBigEndian.length);
      //HexDumper.dumpInHex("sign issue", arrayToConvertToBigEndian);
      final byte[] result = new byte[expectedNumberOfBytes];
      for(int i=0; i<expectedNumberOfBytes; i++)
      {
        result[i] = arrayToConvertToBigEndian[i+1];
      }
      ArrayUtils.reverse(result);
      return result;
    }

    ArrayUtils.reverse(arrayToConvertToBigEndian);
    return arrayToConvertToBigEndian;
  }

  public static boolean checkALineOfInput(final String lineTocheck, final int lineNumber)
  {
    final String valueLine = lineTocheck.replaceAll("[^"+Common.BASE56_CHAR_STR+"]", "");
    if (valueLine.isBlank())  return false;
    final String checkLine = valueLine.substring(0, valueLine.length()-1);
    final char actualCheckChar = valueLine.charAt(valueLine.length()-1);
    final char expectedCheckChar = Common.calculateCheckDigit(checkLine, lineNumber);
    return actualCheckChar == expectedCheckChar;
  }
}
 
Last edited:

kalaspuffar

Well-known member
May 19, 2018
269
91
Sweden
coderinsights.com
Hi @PHolder

I downloaded your example and added my test cases from the Android project for different test identities and the result is not even close to the right value.

I will be honest and say that it's quite late here and I might have done something completely wrong when I created the test cases. Hopefully, you can point me in the right direction.

All the code can be downloaded at the repository below and you can send any pull request fixing all the errors I've introduced :)


Best regards
Daniel
 

PHolder

Well-known member
May 19, 2018
918
124
Hey @kalaspuffar:

Hmm.. I don't know if I tried going from decode to encode... but I do have test cases for encode to decode... it's possible my code has an Endianess issue or something... one of the problems of "testing" it in isolation from a real S4 data structure I suppose. I didn't use any valid SQRL data as input to my encode test, I just used random arrays (and lots of other patterns that aren't particularly relevant to SQRL, like 0,1,2,3...0xa .)

In any case, I'll include some of my test cases before I head off to see what yours look like:

For the Decoder:
Code:
  // https://sqrl.grc.com/threads/size-of-textual-version.442/#post-2746
  @Test
  public void testFromSQRLForums()
  {
    // most of the checking is done in the encode testing
    final String[] lines = {
        "TUkw cv39 M947 VKgk 8SYd",
        "xscJ B7UE Xsip hHbK E2i8",
        "hnKx Fm28 RH7J hx9Z Ea42",
        "MRVr uwea YyZb YRMC 9ZmV",
        "iKiQ Zn9w QZFY XUCp iNwc",
        "Z38p 34L"
    };
    final byte[] result = Base56Decoder.base56Decode(lines);
    // HexDumper.dumpInHex(result);
  }

  // https://sqrl.grc.com/threads/android-v1-5-0-alpha.849/#post-7274
  @Test
  public void test2FromSQRLForums()
  {
    // most of the checking is done in the encode testing
    final String[] lines = {
        "jwvG 2Ee7 cTT5 5NxV t5Ja",
        "8b32 urmm mvbY yMDM KQR3",
        "Q2eX MsAK JCYg 6Sqa ihcN",
        "69s8 P3re Qz2x xhy4 eRyD",
        "gTc3 F5zr SmMh SF9S wrDq",
        "RAU7 E2u"
    };
    final byte[] result = Base56Decoder.base56Decode(lines);
    // HexDumper.dumpInHex(result);
  }

For the Encoder:
Code:
  @Test
  public void testBase56Encode1()
  {
    final byte[] testArray = new byte[] {0x00};
    doTest(testArray);
  }

  @Test
  public void randomArrays()
  {
    final int numberOfTests = 100;
    for (int i=0; i<numberOfTests; i++)
    {
      final int arraySize = rand.nextInt(200);
      final byte[] testArray = new byte[arraySize];
      rand.nextBytes(testArray);
      // HexDumper.dumpInHex(testArray);
      final String encodeResult[] = Base56Encoder.base56Encode(testArray);
      //for (final String s: encodeResult)
      //{
      //  System.out.println(s);
      //}
      final byte[] decodeResult = Base56Decoder.base56Decode(encodeResult);
      // HexDumper.dumpInHex(decodeResult);
      assertIdenticalArrays(testArray, decodeResult);
    }
  }

  @Test
  public void testBase56FilledArray()
  {
    for (int i=0; i<256; i++)
    {
      for (int j=1; j<32; j++)
      {
        final byte[] testArray = arrayFullOf(j, (byte)i);
        doTest(testArray);
      }
    }
  }

  private static byte[] arrayFullOf(final int arraySize, final byte val)
  {
    final byte[] result = new byte[arraySize];
    // Arrays.fill(result, val);  // Arrays.fill() is from BouncyCastle
    for (int i=0; i<arraySize; i++) result[i] = val;
    return result;
  }

  private static void doTest(final byte[] testArray)
  {
    doTest(testArray, false);
  }

  private static void doTest(final byte[] testArray, final boolean debugOutput)
  {
    if (debugOutput) HexDumper.dumpInHex(testArray);
    final String encodeResult[] = Base56Encoder.base56Encode(testArray);
    if (debugOutput) dumpLines(encodeResult);
    final byte[] decodeResult = Base56Decoder.base56Decode(encodeResult);
    //HexDumper.dumpInHex(decodeResult);
    assertIdenticalArrays(testArray, decodeResult);
  }

  private static void dumpLines(final String[] encodeResult)
  {
    for (final String s: encodeResult)
    {
      System.out.println(s);
    }
  }

  static void assertIdenticalArrays(final byte[] array1, final byte[] array2)
  {
    String message = "";
    for(int i=0; i<Math.min(array1.length, array2.length); i++)
    {
      if (array1[i] != array2[i])
      {
        message = "First difference at position " + i;
        break;
      }
    }
    if (array1.length != array2.length)
    {
      System.out.println("Array lengths do not match");
      if (!message.isBlank())
      {
        System.out.println(message);
      }
      HexDumper.dumpInHex("array1", array1);
      HexDumper.dumpInHex("array2", array2);
      assertEquals(array1.length, array2.length);
    }
    if (!message.isBlank())
    {
      System.out.println(message);
      fail();
    }
  }
 

PHolder

Well-known member
May 19, 2018
918
124
@kalaspuffar:

There is an issue with your split function, you're not encoding a full string, the last part is being left off (see the marked line I added):

Code:
  private String[] splitString(String testIdentity)
  {
    final List<String> strings = new ArrayList<>();
    while (testIdentity.length() > 20)
    {
      strings.add(testIdentity.substring(0, 20));
      testIdentity = testIdentity.substring(20);
    }
****    if (!testIdentity.isBlank()) strings.add(testIdentity);  ****

    return strings.toArray(new String[strings.size()]);
  }

And we may be using different testing libraries, but your assertEquals() is backwards compared to what I use:
Code:
final String actual = mergeStrings(encoded);
assertEquals("Encoding should be the same before and after",  testIdentity, actual);
without that change I was seeing:

514

With these two changes, that test case passes for me, so I expect my code is working properly.
 

Attachments

Last edited:
  • Like
Reactions: kalaspuffar

kalaspuffar

Well-known member
May 19, 2018
269
91
Sweden
coderinsights.com
Hi @PHolder

It was late yesterday :)

The test library is strange, different versions want the assertions different ways. The library I got from Maven in intellj wanted it one way and in Android studio the other.

I'll add the last row as well. It was another barrier to test the code splitting it up, when it was late I make stupid mistakes :)

Best regards
Daniel