Create Publication

We are looking for publications that demonstrate building dApps or smart contracts!
See the full list of Gitcoin bounties that are eligible for rewards.

Solution Thumbnail

How to Sign a Transaction By Password: OTP-based Approach

Overview

So you want to sign a transaction using a short easy to remember password. You have an option to store your Algorand private key encrypted by the encryption key derived from the password. It is the way MyAlgo and AlgoSigner work. This approach is simple, robust, and secure.

In this article, we present a very different way to perform password-based authentication. The proposed scheme does not internally use an Algorand private key except the setup stage. Why can one be interested in such a scheme?

First, it’s an exciting challenge to test if the Algorand toolkit allows us to sign transactions securely without using a private key.

Second, a scheme without internal use of an Algorand private key would not make it exposed after being compromised. So one can employ this scheme to send some low-impact transactions without access to a trusted device.

The following sections describe the proposed scheme and the particular PyTEAL code for smart contracts. We explain the specific Python script implementing all steps of the protocol.

Also, we provide a proof-of-concept DApp to demonstrate the described scheme. It consists of two parts: a bunch of Python scripts and a web app. The Python part works on Python Algorand SDK. The web app is based on react-redux and utilizes JS Algorand SDK. You can find the code on GitHub.

Note that there are different approaches to signing transactions using a password without potentially compromising an account’s private key. These other schemes might be more suitable for practical use. Notably, one can apply a password hashing function to derive a secret key from a password and then use it as a private key of the signature scheme. The corresponding public key can be hard-coded into a logical signature that confirms whether the transaction ID was signed with the specified public key. However, our solution does not need to use actual elliptic cryptography, which can be advantageous in some cases.

Brief Protocol Description

Setup phase

  1. Generate a random password. We emphasize that one should strengthen the password by applying password hashing such as PBKDF2 to minimize the risk of a successful dictionary attack.
  2. Derive a sequence of one-time-passwords (OTPs) from the password and commit them to the local state of the particular smart contract (see below for a detailed description).
  3. Store the set of signed logic signatures for use in the next phase. This data is considered public.

Transaction signing phase

We consider only the case of sending one transaction in this solution. One can use this scheme with only slight changes for signing a group transaction, where various users authenticate different transactions.

Let tx be a transaction user wants to send to the ledger. In the following steps, all the transactions are signed by logic signatures prepared earlier.

  1. Check if the local state of the smart contract is ready for a new round.
  2. Make a group transaction (tx, confirm_tx), where confirm_tx is an application call transaction with an OTP. Get confirm_tx_id - an identifier of the confirm_tx transaction in the group.
  3. Store confirm_tx_id to the local state of the smart contract through another application call transaction with another OTP. We refer to this transaction as a prepare transaction.
  4. Check if confirm_tx_id was correctly stored in the local state of the smart contract. This verification is crucial as an Adversary could intercept the previous transaction and commit another identifier.
  5. Send the prepared group transaction. The transaction confirm_tx will be approved if its identifier is equal to the one committed on step 2, and the OTP is correct. The transaction tx will only be approved if confirm_tx is approved as it is a part of the group transaction.

The key idea behind the protocol is that the user commits transaction identifier using an OTP and publishes another OTP if the identifier was actually stored in the ledger. The transaction gets authenticated if this last step was successful.

It is crucial not to permit an Adversary to forge confirmation. The OTPs we use are somewhat interchangeable, and the Adversary can potentially use OTPs from other steps to use in a confirmation request. So the user has to check the local state before he sends any OTP.

If any of the two check steps fails, the user should send the application call transaction with a third OTP to cancel the current round and return to step 1.

Detailed protocol description

Primitives

  • H - a hash function (e.g. sha256).
  • PassDApp - a stateful smart contract.
  • prepareLSig, confirmLSig, confirmTxLSig, cancelLSig - logic signatures.

One-time-passwords

We use OTPs generation and verification principle borrowed from Lamport’s paper Password Authentication with Insecure Communication.

According to Lamport’s method, one should choose a length of OTPs sequence to generate. There is no method to renew a sequence, so a user has to generate a new password to get a new bunch of OTPs when the old ones run out. It is not a restrictive limitation as one can choose N large enough (e.g., 1000000).

Let’s show how we make N one-time passwords from one user password. The sequence of OTPs will look like H(password), H(H(password)), …, H(H(H(…(password)…)=H^N(password).

A user publishes H^{N+1}(password) to commit the whole sequence. Then he utilizes OTPs one by one, going through the sequence in reverse order. To check if an OTP is correct, one can check if H(OTP) = \<previously sent OTP>.

In the current scheme, we use the same sequence of OTPs for three different types of transactions. There is a risk that an Adversary will intercept a cancellation transaction and use its OTP for a confirmation transaction. To prevent this scenario, we allow OTP with index k (i.e., OTP = H^k(password)) to be used in one of the following types of transactions depending on the value of k:

  • prepare – k mod 3 = 0,
  • confirm – k mod 3 = 1,
  • cancel – k mod 3 = 2.

Let’s consider an example. Assume that the last used transaction has an OTP index 500, and the user wants to send prepare and confirm transactions. Then he uses H^498(password) as an OTP for the first one and H^496(password) for the second.

Note that an Adversary can intercept the confirmation transaction and derive cancellation OTP H^497(password) from it. But it is not a big deal as it is only the cancellation that she can perform with this OTP. Anyway, the Adversary could already intercept transactions, and the ability to cancel transactions does not add much to her potential.

Smart Contract

All OTP-related logic we place in the stateful smart contract. It does not have global states and does have three local states. Here’s the list of them:

  • counter – the index of the last used OTP,
  • secret – the value of the last used OTP,
  • mark – the identifier of the transaction group currently being confirmed.

The following PyTEAL code directs the smart contracts approval check.

approval_program = Cond(
  [Txn.application_id() == Int(0), Return(Int(1))],
  [Txn.on_completion() == OnComplete.DeleteApplication, Return(Txn.sender() == Global.creator_address())],
  [Txn.on_completion() == OnComplete.UpdateApplication, Return(Int(0))],
  [Txn.on_completion() == OnComplete.CloseOut, Return(Int(1))],
  [Txn.on_completion() == OnComplete.OptIn, register],
  [Txn.application_args[0] == Bytes("setup"), setup],
  [Txn.application_args[0] == Bytes("prepare"), prepare],
  [Txn.application_args[0] == Bytes("confirm"), confirm],
  [Txn.application_args[0] == Bytes("cancel"), cancel]
)

Variables register, setup, prepare, and confirm denote particular approval checks and actions for different user requests.

The opt-in transaction invokes the register subprocedure.

register = Seq([
  App.localPut(Int(0), Bytes("counter"), Int(0)),
  App.localPut(Int(0), Bytes("secret"), Bytes("")),
  App.localPut(Int(0), Bytes("mark"), Bytes("")),
  Return(Int(1))
])

The user commits the OTP sequence to the smart contract during the setup phase of the protocol described above. Specifically, he sends the app call transaction of the form [setup, H^1000(password), 1000] to the ledger. And here is the code for the approval subprocedure for this transaction.

setup = Seq([
  Assert(Txn.application_args.length() == Int(3)),
  App.localPut(Int(0), Bytes("secret"), Txn.application_args[1]),
  App.localPut(Int(0), Bytes("counter"), Btoi(Txn.application_args[2])),
  App.localPut(Int(0), Bytes("mark"), Bytes("")),
  Return(Int(1))
])

Recall the brief description of the protocol. There were three app call transactions at the signing phase of the protocol:

  • the prepare transaction mentioned at step 2,
  • the confirm transaction named confirm_tx,
  • and the cancel transaction.

Prepare transaction

Let k be the current value of the counter local state of the smart contract.

The call app prepare transaction should have the following arguments list.

[*prepare*, OTP, confirm_tx_id].

The OTP must be equal to H^k’(password), where k’ is the integer dividable by 3 nearest to k, k’\<k. The following approval subprocedure will check and store the OTP, set the mark local state to confirm_tx_id, and update the counter local state.

hash_secret = ScratchVar(TealType.bytes)
prepare = Seq([
  Assert(Txn.application_args.length() == Int(3)),

  # Check if the app is in waiting to prepare state. 
  # This check is not required by the protocol, it is here just
  # to clarify things.
  Assert(Bytes("")==App.localGet(Int(0), Bytes("mark"))),

  # After a secret is acquired counter must be dividable by 3
  hash_secret.store(Sha256(Txn.application_args[1])),
  App.localPut(Int(0), Bytes("counter"), App.localGet(Int(0), Bytes("counter"))-Int(1)),
  If(
    Mod(App.localGet(Int(0), Bytes("counter")), Int(3)) != Int(0),
    Seq([
      hash_secret.store(Sha256(hash_secret.load())),
      App.localPut(Int(0), Bytes("counter"), App.localGet(Int(0), Bytes("counter"))-Int(1)),
    ])
  ),
  If(
    Mod(App.localGet(Int(0), Bytes("counter")), Int(3)) != Int(0),
    Seq([
      hash_secret.store(Sha256(hash_secret.load())),
      App.localPut(Int(0), Bytes("counter"), App.localGet(Int(0), Bytes("counter"))-Int(1)),
    ])
  ),

  # Assert H^d(OTP) = secret, where d = old_counter-counter
  Assert(hash_secret.load()==App.localGet(Int(0), Bytes("secret"))),
  App.localPut(Int(0), Bytes("secret"), Txn.application_args[1]),
  App.localPut(Int(0), Bytes("mark"), Txn.application_args[2]),
  Return(Int(1))
])

Confirm transaction

The confirm transaction would have the following arguments.

[*confirm*, OTP].

Here OTP must be equal to H^(k’-2)(password).

The approval procedure for this transaction will check and store the OTP, clear the mark local state, and update the counter local state.

confirm = Seq([
  Assert(Txn.application_args.length() == Int(2)),
  Assert(Sha256(Sha256(Txn.application_args[1]))==App.localGet(Int(0), Bytes("secret"))),
  Assert(Txn.tx_id()==App.localGet(Int(0), Bytes("mark"))),
  App.localPut(Int(0), Bytes("counter"), App.localGet(Int(0), Bytes("counter"))-Int(2)),
  App.localPut(Int(0), Bytes("secret"), Txn.application_args[1]),
  App.localPut(Int(0), Bytes("mark"), Bytes("")),
  Return(Int(1))
])

Cancel transaction

And finally, the cancel transaction would have arguments.

[*cancel*, OTP].

OTP must be equal to H^(k’-1)(password). As in previous cases, the procedure will check and update the OTP, the counter local state, and clear the mark local state.

cancel = Seq([
  Assert(Txn.application_args.length() == Int(2)),
  Assert(Sha256(Txn.application_args[1])==App.localGet(Int(0), Bytes("secret"))),
  App.localPut(Int(0), Bytes("counter"), App.localGet(Int(0), Bytes("counter"))-Int(1)),
  App.localPut(Int(0), Bytes("secret"), Txn.application_args[1]),
  App.localPut(Int(0), Bytes("mark"), Bytes("")),
  Return(Int(1))
])

Schema

The overall schema of the smart contract looks like

dapp = {
  "local_schema": transaction.StateSchema(1, 2),
  "global_schema": transaction.StateSchema(0, 0),
  "approval_program": compileTeal(approval_program, mode=Mode.Application, version=3),
  "clear_program": compileTeal(Int(1), mode=Mode.Application, version=3)
}

Logic signatures

Each transaction appearing in the protocol has its specific logic signature.

All mentioned logic signatures incorporate the app_id parameter. It is hardcoded before compilation.

Logic signatures for call app transactions (prepare, confirm, and cancel) check that the arguments list is correct: a keyword in the first argument is appropriate, and an application id is valid.

def prepare_lsig_program(app_id):        
  return And(
    Txn.fee() <= Int(1000),
    Txn.application_id() == Int(app_id),
    Txn.on_completion() == OnComplete.NoOp,
    Txn.application_args[0] == Bytes("prepare")
  )

def confirm_lsig_program(app_id):
  return And(
    Txn.fee() <= Int(1000),
    Txn.application_id() == Int(app_id),
    Txn.on_completion() == OnComplete.NoOp,
    Txn.application_args[0] == Bytes("confirm")
  )

def cancel_lsig_program(app_id):
  return And(
    Txn.fee() <= Int(1000),
    Txn.application_id() == Int(app_id),
    Txn.on_completion() == OnComplete.NoOp,
    Txn.application_args[0] == Bytes("cancel")
  )

The logic signature for a user transaction has a more strict policy. The transaction must be a part of a group that includes a confirm transaction, and the sender of the confirm transaction should be the same as the sender of the signed transaction. This logic should also include any additional checks to mitigate the potential damage if the password is compromised.

def confirm_tx_lsig_program(app_id):
  return Seq([
    Assert(Txn.rekey_to() == Global.zero_address()),
    Assert(Gtxn[Btoi(Arg(0))].sender() == Txn.sender()),
    Assert(Gtxn[Btoi(Arg(0))].application_id() == Int(app_id)),
    Assert(Gtxn[Btoi(Arg(0))].on_completion() == OnComplete.NoOp),
    Return(Gtxn[Btoi(Arg(0))].application_args[0] == Bytes("confirm"))
  ])

Implementation

Here we give a detailed description of how to set up and use described protocol implemented in Python. You can explore the GitHub repository for a JS realization and working Python scripts.

You should already have Python 3.9 and py-algorand-sdk installed.

Preparing smart contracts

Connecting to a node

First, let’s set up access to an Algorand node. This node should have the EnableDeveloperAPI flag turned on. It will enable support of TEAL compilation (see docs). This restriction applies only at the build stage. Interactions with a user include no TEAL compilation.

Here is a Python code covering initialization for PureStake.

from algosdk.v2client import algod, indexer
token = "<PURESTAKE API TOKEN>"
algod_client = algod.AlgodClient(
  token, 
  "https://testnet-algorand.api.purestake.io/ps2", 
  {"X-Api-key": token}
)
indexer_client = indexer.IndexerClient(
  "<TOKEN>", 
  "https://testnet-algorand.api.purestake.io/idx2", 
  {"X-Api-key": token}
)

Note that to connect to a bare Algorand node (e. g., through Sandbox), one should use another header key for a token: X-Algo-API-Token.

Specifying a developer account

You need to set a secret mnemonic phrase mnem for a developer account to proceed further. If you don’t have one, you can generate it using the following code.

from algosdk import account, mnemonic

def generateMnemonic():
    [private, address] = account.generate_account()
    return mnemonic.from_private_key(private)
mnem = generateMnemonic()

For the later use, we need to extract the address and private key from the developer mnemonic.

developer_address = mnemonic.to_public_key(mnem)
developer_key = mnemonic.to_private_key(mnem)

Creating the app

In the section Schema, we introduced the full description of the stateful smart contract and put it into the dapp variable. Let’s use it to deploy the app to the ledger.

from algosdk.future import transaction

tx_create_sent = algod_client.send_transaction(
  transaction.ApplicationCreateTxn(
    developer_address, algod_client.suggested_params(), transaction.onComplete.NoOpOC.real,
    dapp["approval_program"], 
    dapp["clear_program"],
    dapp["global_schema"], 
    dapp["local_schema"]
  ).sign(developer_key)
)

Of course, it is necessary to retrieve the app id of the created app. We need to wait for a confirmation of the transaction in order to do this. This procedure is quite typical, but we need to add one extra step for later use: “wait for the next round.”

def wait_for_confirmation(txid, wait_for_next_round=False):
  last_round = algod_client.status().get('last-round')
  txinfo = algod_client.pending_transaction_info(txid)
  while not (txinfo.get('confirmed-round') and txinfo.get('confirmed-round') > 0):
    print('Waiting for confirmation')
    last_round += 1
    algod_client.status_after_block(last_round)
    txinfo = algod_client.pending_transaction_info(txid)
  print('Transaction confirmed in round', txinfo.get('confirmed-round'))

  if wait_for_next_round:
    print('Waiting for current block to be assimilated')
    last_round = algod_client.status().get('last-round')
    algod_client.status_after_block(last_round+1)
  return txinfo

We explain the flag wait_for_next_round later. Here we run the default version of this method to get an app id.

tx_create_info = wait_for_confirmation(tx_create_sent)
app_id = tx_create_info["application_index"]

Preparing logic signatures

As we already have the app id, it is time to compile logic signatures. We need to do two steps: compile PyTEAL to TEAL code and then compile TEAL to bytecode.

prepare_lsig_teal = compileTeal(prepare_lsig_program(app_id), mode=Mode.Signature, version=3)
confirm_lsig_teal = compileTeal(confirm_lsig_program(app_id), mode=Mode.Signature, version=3)
confirm_tx_lsig_teal = compileTeal(confirm_tx_lsig_program(app_id), mode=Mode.Signature, version=3)
cancel_lsig_teal = compileTeal(cancel_lsig_program(app_id), mode=Mode.Signature, version=3)
prepare_lsig_compiled = algod_client.compile(prepare_lsig_teal)
confirm_lsig_compiled = algod_client.compile(confirm_lsig_teal)
confirm_tx_lsig_compiled = algod_client.compile(confirm_tx_lsig_teal)
cancel_lsig_compiled = algod_client.compile(cancel_lsig_teal)

As for our web-app implementation, we save these values to a dapp.json in a pre-build stage. So, the web app does not need to compile TEAL.

Adding a random salt

A salt is an important ingredient for strengthening a password against the dictionary attack: it prevents attackers from pre-computation of the hash tables. The best bet is to provide each user with their own random salt. However, this requires the user to identify himself before using the salt and, therefore, before using a password. No problem if the user has a login, but he only has a password in our case.

So we switch the generation of a random salt from per-user mode to a per-application mode: the new portion of a random salt is generated every time a new application is created.

from nacl.utils import random

pbkdf2_salt = random(32)

User interactions

A typical scenario will look like this.

  1. The user sets up a password using his private key.
  2. Then, he publishes some transactions utilizing the password.

When the time comes, the user renews a password by repeating step 1.

It is crucial to prevent renewing a password during step 2. The reason is not to let an attacker prolong her credentials if she somehow got the compromised password. Moreover, we emphasize that only a limited spectrum of transactions should be allowed to be signed by a password (e. g., micro-payments). However, we consider this question out of the scope of this article and do not specify particular restrictions here.

We provide a Python script that gives an example of how to implement steps 1 and 2.

Also, we demonstrate how the proof-of-concept web app will perform appropriate operations. The first step is to connect to a node. The easiest way is to register on PureStake and paste an API token in the input field (1). Then press the Save button (2). The web app does not store this value anywhere, but it is more secure to use a token from a test account you create for such a case.

Setting a password

Suppose that the user has the private key user_key that corresponds to the address user_address.

First, we sign all necessary logic signatures. Note that we’ve already prepared compiled signatures in previous steps.

def makeLSig(private, compiled):
  lsig = transaction.LogicSig(base64.decodebytes(compiled.encode()))
  lsig.sign(private)
  return lsig

lsigs_kit = {
  "address": user_address,
  "prepare": makeLSig(user_key, prepare_lsig_compiled),
  "confirm": makeLSig(user_key, confirm_lsig_compiled),
  "confirm_tx": makeLSig(user_key, confirm_tx_lsig_compiled),
  "cancel": makeLSig(user_key, cancel_lsig_compiled)
}

Next, we generate a password.

passwordRaw = " ".join(generateMnemonic().split()[:4])

Apply password hashing. For a JS solution, see our code or AlgoSigner implementation. Note also that there are better alternatives to PBKDF2, but it is hard to find one fast enough in a browser. Out of a browser, one should consider scrypt or argon2, which requires a lot of memory for evaluation.

import hashlib

def pbkdf2_hash_password(salt, passwd, iterations_count):  
  return hashlib.pbkdf2_hmac('sha256', passwd.encode("UTF8"), salt, iterations_count)

password = pbkdf2_hash_password(
  pbkdf2_salt, 
  passwordRaw, 
  1000000 # at least 1,000,000, and better is 5,000,000 - do not use the values from the internet, which are way too low
)

And define a function that derives the k-th OTP from the password.

def secret_iterate(password, k):
  i = 0
  h = password
  while i<k:
    m = hashlib.sha256()
    m.update(h)
    h = m.digest()
    i = i+1
  return h

As we’ve generated the password, it should be committed to the dApp. Also, we opt-in if it is needed.

try:
  algod_client.send_transaction(
    transaction.ApplicationOptInTxn(
      user_address, algod_client.suggested_params(), app_id
    ).sign(user_key)
  )
except:
  pass
tx_setup_password = algod_client.send_transaction(
  transaction.ApplicationNoOpTxn(
    user_address, algod_client.suggested_params(), app_id,
    ["setup", secret_iterate(passwd, 1000), (1000).to_bytes(8, 'big')]
  ).sign(user_key)
)

Next, we wait until the smart contract local state is updated. One can do it using the extended call to the method wait_for_confirmation.

wait_for_confirmation(tx_setup_password, wait_for_next_round=True)

The reason for waiting for an additional round is that the ledger might not update the local state of the smart contract in the round in which the transaction was published.

You can perform the described procedure on the web app as follows.

  1. Enter your mnemonic phrase (we do not store this value, but you should not use any real secrets). You also can create a new mnemonic.
  2. Press the “Save” button. The account status will be updated and shown on the left panel; if your balance is low, feel free to get some money from the dispenser (look at the bottom text on the page).
  3. Press the “Opt-in” button. The site will indicate the status of the request on the left panel.
  4. Generate a password. You can do it on your own, but remember that password should be strong.
  5. Press the “Setup” button.
  6. Copy the password to the buffer. You will use it soon.

Publishing a transaction

Let tx be a transaction the user wants to publish to the ledger. For completeness, we give the example definition for tx.

params = algod_client.suggested_params()
gh = params.gh
first_valid_round = params.first
last_valid_round = params.last
fee = params.min_fee
send_amount = amount
tx = transaction.PaymentTxn(
  user_address, 
  fee, 
  first_valid_round, 
  last_valid_round, 
  #recepient address
  gh, "QC7XT7QU7X6IHNRJZBR67RBMKCAPH67PCSX4LYH4QKVSQ7DQZ32PG5HSVQ", 
  110000, 
  flat_fee=True
)

In the following actions, we utilize data from lsigs_kit and password variables. The actual application should get a password from user input and request the logic signatures from a database. One can use the value of the first OTP as a key for this request (e. g., request_key=secret_iterate(password, 1000)).

Our web app utilizes the Algorand ledger itself to store logic signatures. We publish the concatenation of a key and a bunch of signed logic signatures through the hint field of a setup call app transaction. To retrieve signatures, we search for a transaction equipped with a hint field having a specified prefix and parse the rest of it. You can find more details in the code at GitHub (see load_lsigs call in a test.py) if you are interested in such a technic.

Recall that we use OTPs to confirm a user’s identity. To derive a particular OTP, we need to know the index of the last approved OTP. The smart contract stores this index k in the counter local state and stores the value of this OTP in the secret local state (i. e., H^k(password)=secret).

Let’s pull out k from the ledger. We need to define methods to retrieve local states and decode them from base64.

import base64
def read_local_states(app_id):
  local_states = algod_client.account_info(lsigs_kit['address'])['apps-local-state']
  for local_state in local_states :
    if local_state["id"] == int(app_id) :
        return local_state["key-value"]
  return None

def get_local_state(local_states, key):
  if (local_states is None): return None
  key64 = base64.b64encode(key.encode("utf-8")).decode("utf-8")
  for kv in self.local_states:
    if kv["key"]==key64:
      return kv["value"]
  return None

def get_local_state_int(local_states, key):
  state = get_local_state(local_states, key)
  if state is None: return None
  return state["uint"]

def get_local_state_bytes(local_states, key):
  state = get_local_state(local_states, key)
  if state is None: return None
  return base64.b64decode(state["bytes"])

def get_local_state_bytes_raw(local_states, key):
  state = get_local_state(local_states, key)
  if state is None: return None
  return state["bytes"]

Here is the k retrieving procedure.

local_states = read_local_states(app_id)
k = get_local_state_int(local_states, "counter")

Code for calculating OTPs needed for prepare, confirm, and cancel transactions.

dk = self.k%3
if dk==0: dk=3
k_prepare = k-dk
k_confirm = k_prepare-2
k_cancel = k_prepare-1
OTP_prepare = secret_iterate(password, k_prepare)
OTP_confirm = secret_iterate(password, k_confirm)
OTP_cancel = secret_iterate(password, k_cancel)

Now we have prepared all necessary values to start the core protocol. As we already described, one should:

  1. prepare a group transaction consisting of tx along with the confirm transaction;
  2. commit the group transaction to the dApp by sending the appropriative prepare transaction;
  3. send the group transaction to the ledger.

The confirm transaction is essentially an OTP container. It is the same with the cancel transaction.

confirm_tx = transaction.ApplicationNoOpTxn(
  lsigs["address"], algod_client.suggested_params(), app_id,
  ["confirm", OTP_confirm]
)

cancel_tx = transaction.ApplicationNoOpTxn(
  lsigs["address"], algod_client.suggested_params(), app_id,
  ["cancel", OTP_cancel]
)

Recall that the transaction tx is the transaction the user wants to publish to the ledger.

At the preparation step of the protocol, one should commit tx’s identifier to the smart contract. Specifically, one should generate a group (tx, confirm_tx) and send the identifier of confirm_tx to the smart contract via the prepare transaction.

The identifier of confirm_tx captures the whole group including tx. The reason is that the identifier of a transaction is a hash of its content, including a group identifier. And the group identifier is a hash of all transactions included in the group. So the identifier of confirm_tx incorporates the hash of tx.

group_id = transaction_calculate_group_id([tx, tx_confirm])
tx_confirm.group = group_id
tx.group = group_id

We need to solve some technical problems to get a properly encoded identifier. In the smart contract approval procedure, the encoding used for transaction identifiers is slightly different from what the Python framework currently offers (i.e., get get_txid()).

def get_bytes_txid_raw(tx):
  tx = encoding.msgpack_encode(tx)
  to_sign = constants.txid_prefix + base64.b64decode(tx)
  txid = encoding.checksum(to_sign)
  # Diff vs tx.get_txid(): exclude the following lines
  # txid = base64.b32encode(txid).decode()
  # return encoding._undo_padding(txid)
  return txid
mark = get_bytes_txid_raw(confirm_tx)
prepare_tx = transaction.ApplicationNoOpTxn(
  lsigs["address"], algod_client.suggested_params(), app_id,
  ["prepare", OTP_prepare, mark]
)

It is necessary to check the local state of the smart contract before proceeding further. The mark state must be empty. Otherwise, one should send the cancellation transaction.

import sys
local_states = read_local_states(app_id)
def send_cancel():
  algod_client.send_transaction(transaction.LogicSigTransaction(
    cancel_tx,
    lsigs_kit["cancel"]
  ))

if get_local_state_bytes("mark")!=b"":
  send_cancel()
  sys.exit("Smart contract state is invalid. Cancel transaction was sent.")

Send prepare_tx and wait for the local state of the contract to be updated. The wait_for_next_round flag enables this wait step in the wait_for_confirmation function (see above how we define it).

wait_for_confirmation(
  algod_client.send_transaction(transaction.LogicSigTransaction(
    prepare_tx,
    lsigs["prepare"]
  )), 
  wait_for_next_round=True
)

Again, we need to wait to get the local state of the smart contract and check if the mark value is correct.

local_states = read_local_states(app_id)
if get_local_state_bytes("mark")!=mark:
  send_cancel()
  sys.exit("Smart contract state is invalid. Cancel transaction was sent.")

Finally, we are ready to send the group. The only non-trivial step that remains is signing the transactions in the group.

For confirm_tx, we use the lsigs_kit[“confirm”] signature (see confirm_lsig_program).

For tx, we use a bit more sophisticated logic signature lsigs_kit[“confirm_tx”] (see confirm_tx_lsig_program). It requires one additional argument which will indicate the position at which confirm_tx is placed in the group. The rationale is to allow transactions authenticated by different passwords to be mixed in the same group. To do this, one should add confirm_tx-like transactions for each user and put their indexes as logic signatures arguments.

confirm_tx_sign = lsigs_kit["confirm_tx"] 
confirm_tx_sign.args = [(1).to_bytes(8, 'big')]
send_transaction([
  transaction.LogicSigTransaction(
    tx,
    confirm_tx_sign
  ),
  transaction.LogicSigTransaction(
    confirm_tx,
    lsigs_kit["confirm"]
  )
)

We will now demonstrate how to send a transaction through the web app. It is a proof-of-concept application that only supports payment transactions. For the sake of simplicity, we have already placed the test values in the form, but you can change them at any time.

  1. Paste the password.
  2. Press “Find credentials.” The app will search for your address and logic signatures based on the last OTP derived from the password (i. e., H^1000(password)).
  3. Press “Prepare.” In this step, the app creates confirm_tx and sends the prepare transaction. After this, the app will display the identifier of confirm_tx (“Raw TxID in group”). Also, you can observe the local state of the smart contract and check whether the “mark” part is correct.
  4. Press “Confirm.” The app will send the group (tx, confirm_tx).

You can press the big button “Sign and Send Payment Transaction” to automatically run through steps 2-4.

Deleting the app

This step is not necessary. If you want to delete the app, you should execute the following code.

algod_client.send_transaction(
  transaction.ApplicationDeleteTxn(
    developer_address, algod_client.suggested_params(), app_id
  ).sign(developer_key)
)

Security Considerations

There are some weak points in the protocol we have described. It is essential to avoid them in actual use.

Dictionary Attack

We publish derivatives of a user’s password in the ledger, and an Adversary has free access to them. So she can brute force over all possible passwords and find the one that belongs to a user by checking its derivatives against the committed values.

Let’s show how high this risk could be. Here we use only 4-word sentences out of a 2048 words dictionary. If we don’t use the password hashing step, an attacker can break our scheme in a matter of hours. Indeed, for the last transactions, it would take 3 * 2^44 hashes to find the password. For a rough estimate, we can consider that one can check 725 MHashs/s with a price of $25/hour (according to this). Here we assume ETH hash to be similar to SHA256 hash, and the software can be adapted (it’s not really, but that gives the correct ballpark). At this rate, it takes 3 * 2^44 / 725*10^6 / 3600 = 20h to break the password at the cost of $500. And it was in 2018, so nowadays, it would be cheaper and faster.

Worse, it would take 16 * 2 ^ 44 bytes = 281TB to store the first 16 bytes of H ^ 1000 (p) for all passwords, which is significant but can be stored in a large organization. This table would be sufficient to break passwords efficiently. Pre-calculating a table is time-consuming, but this is not an issue as it is feasible.

Luckily, we added a password hashing step, and this horrible scenario is gone. However, recall that our scheme is not entirely immune to the hash table attack (see the Adding a random salt section). Thus, it may be safer to increase the password length to 5 or 6 words.

Checking a local state of a smart contract

The security of the protocol relies heavily on the ability to reliably verify the local state of the smart contract. Algorand satisfies this requirement but only when a user owns a node. It is not the case when a user utilizes a web app. So one may want to add some redundancy and ask several independent nodes for a local state.

This solution is intended for learning purposes only. It does not cover error checking and other edge cases; therefore, it should not be used as a production application.

Acknowledgement

Thanks to the Algorand team for this opportunity to be a part of this developing community.

And also, I am incredibly grateful to Fabrice Benhamouda for his invaluable help in countering the dictionary attack and pointing out the simpler solution. It was he who did all the calculations listed in the Dictionary Attack section.

Image source: @franckinjapan