Commit: 94953674f2f2c1543dec57e5542a26300c8bf4c2 Author: Vi Grey Date: 2024-10-31 06:40 UTC Summary: Add docs and use Secret rows instead of columns Added * RFC style documentation for specification Changed * Use rows of Secret instead of columns for answer * Print answer value instead of "true" if correct answer * Don't print "false" if incorrect answer CHANGELOG.txt | 11 +++ Makefile | 5 ++ docs/gestumblindi-spec.txt | 367 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/docs/gestumblindi-spec.xml | 169 ++++++++++++++++++++++++++++++++++++ src/flags.go | 10 ++- src/gestumblindi.go | 5 +- src/verification.go | 6 +- 7 files changed, 563 insertions(+), 10 deletions(-) diff --git a/CHANGELOG.txt b/CHANGELOG.txt index b570924..ddc96b8 100644 --- a/CHANGELOG.txt +++ b/CHANGELOG.txt @@ -2,6 +2,17 @@ All notable changes to this project will be documented in this file. +## [0.0.2] - 2024-10-31 + +### Added +* RFC style documentation for specification + +### Changed +* Use rows of Secret instead of columns for answer +* Print answer value instead of "true" if correct answer +* Don't print "false" if incorrect answer + + ## [0.0.1] - 2024-10-22 ### Added diff --git a/Makefile b/Makefile index 8554100..4db2259 100644 --- a/Makefile +++ b/Makefile @@ -1,4 +1,5 @@ PKG_NAME := gestumblindi +DOC_NAME := gestumblindi-spec CURRENTDIR := $(dir $(realpath $(firstword $(MAKEFILE_LIST)))) all: @@ -8,5 +9,9 @@ all: cd $(CURRENTDIR); \ #upx --brute $(CURRENTDIR)build/bin/$(PKG_NAME); \ +documents: + mkdir -p $(CURRENTDIR)build/docs; \ + xml2rfc $(CURRENTDIR)src/docs/$(DOC_NAME).xml -p $(CURRENTDIR)build/docs --text --v3 -P + clean: rm -rf -- $(CURRENTDIR)build; \ diff --git a/docs/gestumblindi-spec.txt b/docs/gestumblindi-spec.txt new file mode 100644 index 0000000..e5ed740 --- /dev/null +++ b/docs/gestumblindi-spec.txt @@ -0,0 +1,367 @@ + + + + +Independent V. Grey + Independent + 31 October 2024 + + +Gestumblindi - Human Calculatable Verification Specification - Version 1 + gestumblindi-spec + +Abstract + + *Gestumblindi* is a specification based heavily on the work from + "Towards Human Computable Passwords" [THCP] to generate challenges + whose correct answers are human calculatable. The purpose of + *Gestumblindi* is to allow a user to provide verification to a + service connected to over a semi-trusted computer - "a computer that + stores information and performs computations correctly but does not + provide confidentiality." + +Table of Contents + + 1. Introduction + 1.1. Overview and Preliminaries + 1.1.1. Notation and Vocabulary + 2. Secret + 3. Challenges + 3.1. Generating Challenges + 3.1.1. Fast Dice Roller Algorithm + 3.2. Answering Challenges + 4. Security + 5. References + 5.1. Normative References + Copyright Notice + Author's Address + +1. Introduction + +1.1. Overview and Preliminaries + + The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", + "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and + "OPTIONAL" in this document are to be interpreted as described in + [BCP14] when, and only when, they appear in all capitals, as shown + here. + +1.1.1. Notation and Vocabulary + + 0b011001 The binary sequence 0, 1, 1, 0, 0, and 1 in that order. + + 0x7F The octet 7F. + + 0x007FFF A sequence of octets 00, 7F, and FF in that order. + + "abc" Literal string 'abc' + + The terms *byte* and *octet* are used interchangeably in this + document. + + All *Unsigned Integers* in this document are big-endian. + + *String* values MUST use UTF-8 [RFC3629] (Section 3) encoding. If an + example of a string value is given, the example will be between + quotation marks ("). The quotation marks are not included in the + string. Not all content between quotation marks will be string value + examples, so be aware of that when continuing through this document. + + *Integer* values MUST be whole numbers. + +2. Secret + + The *Secret* is a string of printable characters. The *Secret* MUST + contain a square number greater of unique characters that do not + include the space character (0x20). Space characters MAY be included + in the *Secret* to help with human readability, but MUST NOT be + interpreted. + + A square number is an integer that is the product of an integer with + itself. For instance, 25 is a square number because it is the + product of 5 and 5, as is 36 because it is the product of 6 and 6, + along with 49 because it is the product of 7 and 7. + + The characters in the *Secret* MUST be in a random order and known + only by the user and the trusted computer the user verifies through. + For instance, if using the letters A-Y, the result ordering may look + something like "UFBNILDVXWJRSCYAHOQMEKTGP". + +3. Challenges + + Each challenge contains 3 random strings of characters chosen + exclusively from the *Secret*. These 3 strings are called the + *Decoupler*, *K1*, and *K2*. The amount of characters in *Decoupler* + MUST be the square of the amount of characters in the *Secret*, so if + the *Secret* is 36 characters in length, *Decoupler* will be 6 + characters in length. The amount of characters in *K2* MUST be 1 + more than twice the amount of characters in *K1*, so if *K1* is 4 + characters in length, *K2* will be 9 characters in length. + + Each challenge has a single non-zero answer between 1 and the length + of the *Decoupler* string (inclusive), so if the length of + *Decoupler* is 6, the possible answers would be 1, 2, 3, 4, 5, and 6. + +3.1. Generating Challenges + + To generate the 3 strings required for a challenge, seemingly random + bits need to be generated. We need to keep track of 2 values, a list + of bits called *Random Bits* and a 512-bit byte array *Latest Hash*. + The difference in structure of *Random Bits* and *Latest Hash* is + that *Random Bits* is a list of binary bits that does not have a set + size and *Latest Hash* is an array of bytes that is always 512 bits + in length. To begin creating the *Random Bits*, we create an + *Initial Hash* by using an HMAC [RFC2104], with SHA-512 [SHS] as the + hashing algorithm, the *Secret* as the secret key, and a 64-bit + unsigned integer called the *Counter* as the message. The *Counter* + is the 0-indexed unsigned integer of the challenge, so the first + challenge has a value of 0, the second challenge has a value of 1, + the third challenge has a value of 2, and so on. The result of this + HMAC will be a 512-bit value that is effectively random. Append + those 512 bits to the list *Random Bits* and set *Latest Hash* to + those 512 bits. + + If more bits are needed in *Random Bits*, perform a SHA-512 hash on + the *Latest Hash* value, append the 512 bits of the result of that + hash to the list *Random Bits*, and set *Latest Hash* to those same + 512 bits. + + The bits in *Random Bits* are converted into random integers between + 0 and the length of the *Secret* string (non-inclusive), so if the + length of the *Secret* is 36, the possible values are 0, 1, 2, 3, 4, + 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, + 23, and 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, and 35. This + value is determined using the *FAST DICE ROLLER* algorithm [FDR]. + The total of random integers needed to produce a challenge is equal + to the length of *Decoupler*, *K1*, and *K2* combined, so if + *Decoupler* is 6 characters long, *K1* is 4 characters long, and *K2* + is 9 characters long, 19 random integers between 0 and 36 (non- + inclusive) will be needed in total. + + Each random integer is a 0-indexed character offset of the *Secret* + string, so 0 is the first character of the *Secret* string, 1 is the + second character, and so on. Using the 25 character long *Secret* + "UFBNILDVXWJRSCYAHOQMEKTGP", having a *K1* length of 4, and a + *Counter* value of 0, the first challenge will be *Decoupler*: + "KEXPL", *K1*: "OVHM", and *K2*: "VIFWYJPMM". + +3.1.1. Fast Dice Roller Algorithm + + function flip() { + a = RandomBits[0] + RandomBits = RandomBits[1:] + return a + } + + function FastDiceRoller(n) { + v = 1 + c = 0 + while true { + v = 2 * v + c = 2 * c + flip() + if v >= n { + if c < n { + return c + } else { + v = v - n + c = c - n + } + } + } + } + + Every time flip() is called, the left-most bit of *Random Bits* is + used up, resulting in *Random Bits* being 1 bit shorter. As + anexample, let's assume *n* is 9, so we're generating a random number + between 0 and 9 (non-inclusive), so either 0, 1, 2, 3, 4, 5, 6, 7, or + 8, and we have a *Random Bits* value of 0b11110100, so the bits, in + order, of 1, 1, 1, 1, 0, 1, 0, 0. In the first loop before the first + if statement, we have *v* = 2, *c* = 1, and *Random Bits* = + 0b1110100. Notice the leftmost bit has been used up and now the + length of *Random Bits* is 7 instead of 8. *v* is not greater than + or equal to *n*, so we go back to the start of the loop. On the + second round of the loop before the first if statement, we have *v* = + 4, *c* = 3, and *Random Bits* = 0b110100. *v* is not greater than or + equal to *n*, so we go back to the start of the loop. On the third + round of the loop before the first if statement, we have *v* = 8, *c* + = 7, and *Random Bits* = 0b10100. *v* is not greater than or equal + to *n*, so we go back to the start of the loop. On the fourth round + of the loop before the first if statement, we have *v* = 16, *c* = + 15, and *Random Bits* = 0b0100. *v* is greater than or equal to *n*, + so we now check if *c* is less than *n*. *c* is not less than *n*, + so we subtract *n* from *v* and *c*. *v* is now 7 and *c* is now 6 + and we go back to the start of the loop. On the fifth round of the + loop before the first if statement, we have *v* = 14, *c* = 12, and + *Random Bits* = 0b100. *v* is greater than or equal to *n*, so we + now check if *c* is less than *n*. *c* is not less than *n*, so we + subtract *n* from *v* and *c*. *v* is now 5 and *c* is now 3 and we + go back to the start of the loop. On the sixth round of the loop + before the first if statement, we have *v* = 10, *c* = 7, and *Random + Bits* = 0b00. *v* is greater than or equal to *n*, so we now check + if *c* is less than *n*. *c* is less than *n*, so our random number + result is 7. This would result in the *Secret* character at offset 7 + (the 8th character) being chosen. + +3.2. Answering Challenges + + To answer challenges, the characters in the *Secret* need to be + understood as a square. With an example 25 character *Secret* of + "UFBNILDVXWJRSCYAHOQMEKTGP", the rows of the square would be "UFBNI", + "LDVXW", "JRSCY", "AHOQM", and "EKTGP". These rows are numbered with + 1-indexing, so the first row is 1, the second row is 2, and so on. + + A running total is kept while answering a challenge. The running + total starts at 0. To begin calculating the answer for a challenge, + take the value of *K1*. As the example, we'll use "OVHM" for *K1*. + For each character in *K1*, add the row number where the character + appears in the *Secret* to the running total. In this example, "O" = + 4, "V" = 2, "H" = 4, and "M" = 4, so the running total will be 0 + 4 + + 2 + 4 + 4 = 14. The next step is to take the remainder when + dividing the running total by the length of *Decoupler*, so in this + case 14 / 5 = 2 remainder 4, making our running total 4. If the + running total is 0 at this point, add the length of *Decoupler* to + the running total. The running total no matter what will be either + equal to or less than the length of *Decoupler*, but greater than 0. + + Now that we have a running total of all of the values of *K1* added + up and normalized to within the length of *Decoupler*, take the + character in *Decoupler* at that 1-indexed position, so 1 is the + first character of *Decoupler*, 2 is the second character, and so on. + We'll use "KEXPL" as an example for *Decoupler* and continue using + the value of 4 for the running total, meaning we take the letter "P" + in this example. Set the running total to the row number where this + from *Decoupler* appears in the *Secret*, so in this case, the + running total is now equal to 5. + + Next, we take the value of *K2*, and for each character in *K2*, we + add the row number where the character appears in the *Secret* to the + running total. As an example, we'll use "VIFWYJPMM" for *K2* and + continue using the value of 5 for the running total. In this + example, "V" = 2, "I" = 1, "F" = 1, "W" = 2, "Y" = 3, "J" = 3, "P" = + 5, "M" = 4, and "M" = 4, so the running total will be 5 + 2 + 1 + 1 + + 2 + 3 + 3 + 5 + 4 + 4 = 30. To get the final answer, take the + remainder when dividing the running total by the length of + *Decoupler*, so in this case 30 / 5 = 6 remainder 0, making our + running total 0. If the running total is 0 at this point, add the + length of *Decoupler* to the running total. This will turn the + running total in this example from 0 to 5. The running total no + matter what will be either equal to or less than the length of + *Decoupler*, but greater than 0. This value is the answer to the + challenge. In this example's case, the answer is 5. + +4. Security + + The probability of guessing the answers to these challenges is 1 / + N^C, where *N* is the length of *Decoupler* and *C* is the amount of + challenges that must be answered to provide successful verification. + For instance, if the length of *Decoupler* is 6 characters and 24 + challenges are provided at a time, the probability of successfully + verifying by guessing is 1 in 4738381338321616896. + + Part of the security of *Gestumblindi* involves the trusted computer + that also knows the *Secret* being limited in how many requests can + be performed per second. In the case of *N* being 6 and *C* being + 24, if 1000000000 attempts could be performed each second, it would + take over 150 years to try all 4738381338321616896 possibilities. + + According to "Towards Human Computable Passwords", there is a limit + to how many random challenges can be answered before an adversary can + reconstruct the order of the *Secret*. That general limit is S^F, + where *S* is the the length of the *Secret* and *F* is the strength + of *F1* and *F2*, which is determined by min(F1+1, (F2+1)/2). For + instance, if the *Secret* is 36 characters in length, *F1* is 4 + characters long, and *F2* is 9 characters long, the amount of + challenges that can be performed are 36^(min(4+1, (9+1)/2)), or + 36^(min(5, 10/2)) or 36^5, which is 60466176 challenges in total. If + 24 challenges are required in each full set of challenges to + successfully verify, then 2519424 sets of challenges can be solved + before the order of the *Secret* should be able to be reconstructed. + + While the length of the *Secret* in theory MAY be any square number + greater than 0 and the length of *K1* MAY be any integer greater than + 0, it is RECOMMENDED that the lengths are sufficiently large as to + take an impractical amount of time to brute force. The faster + attempts can be made on the trusted computer, the larger the length + of *Secret* should be and the more often challenges are successfully + answered, the larger *K1* should be. It is RECOMMENDED that the + length of the *Secret* be at least 36 and the length of *K1* be at + least 4. + +5. References + +5.1. Normative References + + [BCP14] Best Current Practice 14, + . + At the time of writing, this BCP comprises the following: + + Bradner, S., "Key words for use in RFCs to Indicate + Requirement Levels", BCP 14, RFC 2119, + DOI 10.17487/RFC2119, March 1997, + . + + Leiba, B., "Ambiguity of Uppercase vs Lowercase in RFC + 2119 Key Words", BCP 14, RFC 8174, DOI 10.17487/RFC8174, + May 2017, . + + [FDR] Lumroso, J., "Optimal Discrete Uniform Generation from + Coin Flips, and Applications", + DOI 10.48550/arXiv.1304.1916, April 2013, + . + + [RFC2104] Krawczyk, H., Bellare, M., and R. Canetti, "HMAC: Keyed- + Hashing for Message Authentication", RFC 2104, + DOI 10.17487/RFC2104, February 1997, + . + + [RFC3629] Yergeau, F., "UTF-8, a transformation format of ISO + 10646", STD 63, RFC 3629, DOI 10.17487/RFC3629, November + 2003, . + + [SHS] NIST, "FIPS PUB 180-4: Secure Hash Standard (SHS)", + DOI 10.6028/NIST.FIPS.180-4, August 2015, + . + + [THCP] Blocki, J., Blum, M., Datta, A., and S. Vempala, "Towards + Human Computable Passwords", DOI 10.48550/arXiv.1404.0024, + September 2016, . + +Copyright Notice + + Copyright (c) 2024, Vi Grey + + All rights reserved. + + Redistribution and use of this documentation in source (XML format) + and/or "compiled" forms (TXT, PDF, HTML, etc), with or without + modification, are permitted provided that the following conditions + are met: + + 1. Redistributions of source code (XML format) of this documentation + must retain the above copyright notice, this list of conditions, + and the following disclaimer in the documentation. + + 2. Redistributions in compiled form (Converted to TXT, PDF, HTML, + and other formats) of this documentation must reproduce the above + copyright notice, this list of conditions, and the following + disclaimer in the documentation. + + THIS DOCUMENTATION IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY + EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR + PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE + FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR + CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF + SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR + BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, + WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE + OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + DOCUMENTATION, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + +Author's Address + + Vi Grey + Independent + Email: vi@vigrey.com + URI: gemini://vigrey.com diff --git a/src/docs/gestumblindi-spec.xml b/src/docs/gestumblindi-spec.xml new file mode 100644 index 0000000..36ceccd --- /dev/null +++ b/src/docs/gestumblindi-spec.xml @@ -0,0 +1,169 @@ + + + + Gestumblindi - Human Calculatable Verification Specification - Version 1 + + + Independent +
+ vi@vigrey.com + gemini://vigrey.com +
+ + + General + Independent + + Gestumblindi is a specification based heavily on the work from "Towards Human Computable Passwords" to generate challenges whose correct answers are human calculatable. The purpose of Gestumblindi is to allow a user to provide verification to a service connected to over a semi-trusted computer - "a computer that stores +information and performs computations correctly but does not provide confidentiality." + + + +
+ Introduction +
+ Overview and Preliminaries + The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT", "SHOULD", "SHOULD NOT", "RECOMMENDED", "NOT RECOMMENDED", "MAY", and "OPTIONAL" in this document are to be interpreted as described in when, and only when, they appear in all capitals, as shown here. +
+ Notation and Vocabulary +
+
0b011001
The binary sequence 0, 1, 1, 0, 0, and 1 in that order.
+
0x7F
The octet 7F.
+
0x007FFF
A sequence of octets 00, 7F, and FF in that order.
+
"abc"
Literal string 'abc'
+
+ The terms byte and octet are used interchangeably in this document. + All Unsigned Integers in this document are big-endian. + String values MUST use UTF-8 encoding. If an example of a string value is given, the example will be between quotation marks ("). The quotation marks are not included in the string. Not all content between quotation marks will be string value examples, so be aware of that when continuing through this document. + Integer values MUST be whole numbers. +
+
+
+
+ Secret + The Secret is a string of printable characters. The Secret MUST contain a square number greater of unique characters that do not include the space character (0x20). Space characters MAY be included in the Secret to help with human readability, but MUST NOT be interpreted. + A square number is an integer that is the product of an integer with itself. For instance, 25 is a square number because it is the product of 5 and 5, as is 36 because it is the product of 6 and 6, along with 49 because it is the product of 7 and 7. + The characters in the Secret MUST be in a random order and known only by the user and the trusted computer the user verifies through. For instance, if using the letters A-Y, the result ordering may look something like "UFBNILDVXWJRSCYAHOQMEKTGP". +
+
+ Challenges + Each challenge contains 3 random strings of characters chosen exclusively from the Secret. These 3 strings are called the Decoupler, K1, and K2. The amount of characters in Decoupler MUST be the square of the amount of characters in the Secret, so if the Secret is 36 characters in length, Decoupler will be 6 characters in length. The amount of characters in K2 MUST be 1 more than twice the amount of characters in K1, so if K1 is 4 characters in length, K2 will be 9 characters in length. + Each challenge has a single non-zero answer between 1 and the length of the Decoupler string (inclusive), so if the length of Decoupler is 6, the possible answers would be 1, 2, 3, 4, 5, and 6. +
+ Generating Challenges + To generate the 3 strings required for a challenge, seemingly random bits need to be generated. We need to keep track of 2 values, a list of bits called Random Bits and a 512-bit byte array Latest Hash. The difference in structure of Random Bits and Latest Hash is that Random Bits is a list of binary bits that does not have a set size and Latest Hash is an array of bytes that is always 512 bits in length. To begin creating the Random Bits, we create an Initial Hash by using an HMAC , with SHA-512 as the hashing algorithm, the Secret as the secret key, and a 64-bit unsigned integer called the Counter as the message. The Counter is the 0-indexed unsigned integer of the challenge, so the first challenge has a value of 0, the second challenge has a value of 1, the third challenge has a value of 2, and so on. The result of this HMAC will be a 512-bit value that is effectively random. Append those 512 bits to the list Random Bits and set Latest Hash to those 512 bits. + If more bits are needed in Random Bits, perform a SHA-512 hash on the Latest Hash value, append the 512 bits of the result of that hash to the list Random Bits, and set Latest Hash to those same 512 bits. + The bits in Random Bits are converted into random integers between 0 and the length of the Secret string (non-inclusive), so if the length of the Secret is 36, the possible values are 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, and 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, and 35. This value is determined using the FAST DICE ROLLER algorithm . The total of random integers needed to produce a challenge is equal to the length of Decoupler, K1, and K2 combined, so if Decoupler is 6 characters long, K1 is 4 characters long, and K2 is 9 characters long, 19 random integers between 0 and 36 (non-inclusive) will be needed in total. + Each random integer is a 0-indexed character offset of the Secret string, so 0 is the first character of the Secret string, 1 is the second character, and so on. Using the 25 character long Secret "UFBNILDVXWJRSCYAHOQMEKTGP", having a K1 length of 4, and a Counter value of 0, the first challenge will be Decoupler: "KEXPL", K1: "OVHM", and K2: "VIFWYJPMM". +
+ Fast Dice Roller Algorithm + = n { + if c < n { + return c + } else { + v = v - n + c = c - n + } + } + } +}]]> + Every time flip() is called, the left-most bit of Random Bits is used up, resulting in Random Bits being 1 bit shorter. As anexample, let's assume n is 9, so we're generating a random number between 0 and 9 (non-inclusive), so either 0, 1, 2, 3, 4, 5, 6, 7, or 8, and we have a Random Bits value of 0b11110100, so the bits, in order, of 1, 1, 1, 1, 0, 1, 0, 0. In the first loop before the first if statement, we have v = 2, c = 1, and Random Bits = 0b1110100. Notice the leftmost bit has been used up and now the length of Random Bits is 7 instead of 8. v is not greater than or equal to n, so we go back to the start of the loop. On the second round of the loop before the first if statement, we have v = 4, c = 3, and Random Bits = 0b110100. v is not greater than or equal to n, so we go back to the start of the loop. On the third round of the loop before the first if statement, we have v = 8, c = 7, and Random Bits = 0b10100. v is not greater than or equal to n, so we go back to the start of the loop. On the fourth round of the loop before the first if statement, we have v = 16, c = 15, and Random Bits = 0b0100. v is greater than or equal to n, so we now check if c is less than n. c is not less than n, so we subtract n from v and c. v is now 7 and c is now 6 and we go back to the start of the loop. On the fifth round of the loop before the first if statement, we have v = 14, c = 12, and Random Bits = 0b100. v is greater than or equal to n, so we now check if c is less than n. c is not less than n, so we subtract n from v and c. v is now 5 and c is now 3 and we go back to the start of the loop. On the sixth round of the loop before the first if statement, we have v = 10, c = 7, and Random Bits = 0b00. v is greater than or equal to n, so we now check if c is less than n. c is less than n, so our random number result is 7. This would result in the Secret character at offset 7 (the 8th character) being chosen. +
+
+
+ Answering Challenges + To answer challenges, the characters in the Secret need to be understood as a square. With an example 25 character Secret of "UFBNILDVXWJRSCYAHOQMEKTGP", the rows of the square would be "UFBNI", "LDVXW", "JRSCY", "AHOQM", and "EKTGP". These rows are numbered with 1-indexing, so the first row is 1, the second row is 2, and so on. + A running total is kept while answering a challenge. The running total starts at 0. To begin calculating the answer for a challenge, take the value of K1. As the example, we'll use "OVHM" for K1. For each character in K1, add the row number where the character appears in the Secret to the running total. In this example, "O" = 4, "V" = 2, "H" = 4, and "M" = 4, so the running total will be 0 + 4 + 2 + 4 + 4 = 14. The next step is to take the remainder when dividing the running total by the length of Decoupler, so in this case 14 / 5 = 2 remainder 4, making our running total 4. If the running total is 0 at this point, add the length of Decoupler to the running total. The running total no matter what will be either equal to or less than the length of Decoupler, but greater than 0. + Now that we have a running total of all of the values of K1 added up and normalized to within the length of Decoupler, take the character in Decoupler at that 1-indexed position, so 1 is the first character of Decoupler, 2 is the second character, and so on. We'll use "KEXPL" as an example for Decoupler and continue using the value of 4 for the running total, meaning we take the letter "P" in this example. Set the running total to the row number where this from Decoupler appears in the Secret, so in this case, the running total is now equal to 5. + Next, we take the value of K2, and for each character in K2, we add the row number where the character appears in the Secret to the running total. As an example, we'll use "VIFWYJPMM" for K2 and continue using the value of 5 for the running total. In this example, "V" = 2, "I" = 1, "F" = 1, "W" = 2, "Y" = 3, "J" = 3, "P" = 5, "M" = 4, and "M" = 4, so the running total will be 5 + 2 + 1 + 1 + 2 + 3 + 3 + 5 + 4 + 4 = 30. To get the final answer, take the remainder when dividing the running total by the length of Decoupler, so in this case 30 / 5 = 6 remainder 0, making our running total 0. If the running total is 0 at this point, add the length of Decoupler to the running total. This will turn the running total in this example from 0 to 5. The running total no matter what will be either equal to or less than the length of Decoupler, but greater than 0. This value is the answer to the challenge. In this example's case, the answer is 5. +
+
+
+ Security + The probability of guessing the answers to these challenges is 1 / NC, where N is the length of Decoupler and C is the amount of challenges that must be answered to provide successful verification. For instance, if the length of Decoupler is 6 characters and 24 challenges are provided at a time, the probability of successfully verifying by guessing is 1 in 4738381338321616896. + Part of the security of Gestumblindi involves the trusted computer that also knows the Secret being limited in how many requests can be performed per second. In the case of N being 6 and C being 24, if 1000000000 attempts could be performed each second, it would take over 150 years to try all 4738381338321616896 possibilities. + According to "Towards Human Computable Passwords", there is a limit to how many random challenges can be answered before an adversary can reconstruct the order of the Secret. That general limit is SF, where S is the the length of the Secret and F is the strength of F1 and F2, which is determined by min(F1+1, (F2+1)/2). For instance, if the Secret is 36 characters in length, F1 is 4 characters long, and F2 is 9 characters long, the amount of challenges that can be performed are 36min(4+1, (9+1)/2), or 36min(5, 10/2) or 365, which is 60466176 challenges in total. If 24 challenges are required in each full set of challenges to successfully verify, then 2519424 sets of challenges can be solved before the order of the Secret should be able to be reconstructed. + While the length of the Secret in theory MAY be any square number greater than 0 and the length of K1 MAY be any integer greater than 0, it is RECOMMENDED that the lengths are sufficiently large as to take an impractical amount of time to brute force. The faster attempts can be made on the trusted computer, the larger the length of Secret should be and the more often challenges are successfully answered, the larger K1 should be. It is RECOMMENDED that the length of the Secret be at least 36 and the length of K1 be at least 4. +
+ + + + References + + Normative References + + + + + + + Optimal Discrete Uniform Generation from Coin Flips, and Applications + + + + + + + + + + FIPS PUB 180-4: Secure Hash Standard (SHS) + + NIST + + + + + + + + Towards Human Computable Passwords + + + + + + + + + + +
+ Copyright Notice + Copyright (c) 2024, Vi Grey + All rights reserved. + Redistribution and use of this documentation in source (XML format) and/or "compiled" forms (TXT, PDF, HTML, etc), with or without modification, are permitted provided that the following conditions are met: +
    +
  1. Redistributions of source code (XML format) of this documentation must retain the above copyright notice, this list of conditions, and the following disclaimer in the documentation.
    2. +
  2. Redistributions in compiled form (Converted to TXT, PDF, HTML, and other formats) of this documentation must reproduce the above copyright notice, this list of conditions, and the following disclaimer in the documentation.
    3. +
+ THIS DOCUMENTATION IS PROVIDED BY THE AUTHOR(S) "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR(S) BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS DOCUMENTATION, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. +
+ + diff --git a/src/flags.go b/src/flags.go index 1041683..1d01379 100644 --- a/src/flags.go +++ b/src/flags.go @@ -11,6 +11,7 @@ import ( var ( answerFlag string configPath string + randomFlag string previewFlag int helpFlag bool versionFlag bool @@ -93,10 +94,11 @@ func displayHelp() { fmt.Printf(`Usage: %s [OPTIONS]... Options: - -a, --answer Returns with exit code 0 if challenge - response is correct, otherwise returns with - exit code 1 - -c, --config Path to config file + -a, --answer Prints and returns with exit + code 0 if challenge response is correct, + otherwise does not print and + returns with exit code 1. + -c, --config Path to config file. -h, --help Print Help (this message) and exit. -p, --preview Show sets of challenges -v, --version Print version and exit. diff --git a/src/gestumblindi.go b/src/gestumblindi.go index cea6534..edf5c38 100644 --- a/src/gestumblindi.go +++ b/src/gestumblindi.go @@ -7,7 +7,7 @@ import ( const ( PROGRAM = "gestumblindi" - VERSION = "0.0.1" + VERSION = "0.0.2" ) func init() { @@ -26,11 +26,10 @@ func main() { if checkAnswer() { configData.Counter += configData.Challenges if err := updateConfigFile(); err == nil { - fmt.Println(true) + fmt.Println(answerFlag) return } } - fmt.Println(false) os.Exit(1) } else if previewFlag < 1 { previewFlag = 1 diff --git a/src/verification.go b/src/verification.go index 8d6f7a8..c6ae0e1 100644 --- a/src/verification.go +++ b/src/verification.go @@ -46,11 +46,11 @@ func getAnswer(challenge []int) int { total := 0 offset := len(challenge) - (k1 + k2) for i := 0; i < k1; i++ { - total += challenge[offset+i] + 1 + total += int(challenge[offset+i]/configData.base) + 1 } - total = challenge[(total+configData.base-1)%configData.base] + 1 + total = int(challenge[(total+configData.base-1)%configData.base]/configData.base) + 1 for i := 0; i < k2; i++ { - total += challenge[offset+k1+i] + 1 + total += int(challenge[offset+k1+i]/configData.base) + 1 } return (total+configData.base-1)%configData.base + 1 }