[Gnuk-users] No Private Key(?) method

[NIIBE Yutaka]

Hello,

While I don't like the expression "secure storage", I come up with an
idea, a method for private key handling.  It's not mature yet.  I'd
like to listen your opinions.

* Current method

Here are figures of current method to encrypt private key
and to decrypt encrypted private key to get private key.


              Salt             Private Key
               |                  |
               V                  V
   Pass  -> [ KDF ] -> DEK -> [ Encryption ] -> Encrypted
   phrase                                       Private Key


              Salt             Encrypted Private Key
               |                  |
               V                  V
   Pass  -> [ KDF ] -> DEK -> [ dencryption ] -> Private Key
   phrase


   KDF: Key Derivation Function

   DEK: Data Encryption Key

Encrypted private key is stored in flash ROM in Gnuk Token.


* "No Private Key" method

The structure is similar (or we can say it's almost same).

              Salt       Private Key
               |            |
               V            V
   Pass  -> [ PRNG ] -> [ Matcher ] --> Sequence to recover Private Key
   phrase

              Salt       Sequence to recover Private Key
               |            |
               V            V
   Pass  -> [ PRNG ] -> [ Decoder ] --> Private Key
   phrase


An example matcher works as follows.

                    <Input Buffer>
                      |     ^
                      |     | Index
                      V     |
                     [RegI] |
                      |     |
                      V     |
                     +--------+
   Random -->[RegR]->| [Reg0] |
   number            | [Reg1] |--> Output
   sequence <--------|        |
              Next   +--------+

(0) RegI <= 0, RegR <= 0, Reg0 <= 0, Reg1 <= 0
(1) Loop from Index = 0 to Index = (Length of Input Buffer)
(1-1) Get next input byte to [RegI] (or finish if none)
(1-2) Loop (until it can output a bit 0)
(1-2-1) Get next random number to [RegR]
(1-2-2) If [Reg0] XOR [RegR] == [RegI] then output 0,
        [Reg0] <= [Reg1], [Reg1] <= 0
        Goto (1-1)
(1-2-3) If [Reg0] XOR [RegR] != [RegI] then output 1,
        [Reg0] <= [Reg0], [Reg1] <= [Reg1] XOR [RegR]
        Go to (1-2-1)

The output is like:

          single 0  single 0
           |         |
           v         v
   1...11110111111..10...
   <------> <------->
    all 1    all 1

Which can be encoded by run-length encoding.

Calculation in (1-2-2) and (1-2-3) could be as simple as comparison of
[RegR] and [Reg0].  In the description above, I "use" all the sequence
of random number.

The decoder does reverse calculation.

(A) In fact, it's another way to encrypt private key (similar to the
    one with One-time pad), but it would be possible for me to insist
    "we don't store private key".

    I believe that given crypto-PRNG, it's as safe as usual encrypted
    private key, while implementation could be simpler.


(B) Sequence to recover Private Key can be redundant (and possibly
    copyrightable)

    == there are multiple ways to represent the Sequence,
       given a input of (pass-phrase, salt, private key),
       by matcher algo and skip of match

I'm considering to take advantage of the fact (B) and protect my
sequence by copyright law, so that I can sue someone who copies
mine. ;-)


Drawback is the Sequence is longer (in general) than usual encrypted
private key.

When you generate private key by given (sequence, passphrase and
salt), the sequence can be shorter than usual encrypted private key in
some encoding (when you will change the passphrase for that, it will
be longer).


Well, the name "No Private Key(?) method" is cheating, are there any
alternatives?
--