-*- mode: text -*-

$Id: HACKING,v 1.5 2002/02/24 01:06:11 hoenicke Exp $


======================================================================
Requirements

 * Can store personal-confidential information

 * Storage should not be the weakest link

 * Should be not-too-hard to decode on a PC, either using a custom
   program or writing one from this document.

 * Should use a well known and researched encryption method.


Packed format of key records:

strz name of record
encrypted:
  strz account name
  strz password
  strz notes

It's OK for any of these fields to be empty.  If they are, we use
the record's unique ID in the list.

New fields may be added at the end.  Note that we must be careful when
parsing them, in case an error in encryption or elsewhere has broken
this format.

Key records are stored unpacked in a KeyRecordType, with all
character pointers to strings allocated elsewhere on the card.

The first record is unencrypted.  After it's trailing NUL comes a
series of ECB DES3 blocks.

Deleted or archived records are always stored at the end of the
database.

Key records are stored encrypted by a random session key.  The session
key in turn is stored encrypted by the password in the application
info block.


Future Plans:

In the next release I would like to extend this format to make it more
flexible and powerful:

UInt16  recordVersion
FontID  nameFont
strz    name of record
encrypted:
  Field  field1
  Field  field2
  ...

where Field is:
  LabelID label
  FontID  font
  strz    value

LabelID is a 8 bit value.  Labels 0..127 are system defined, 128..255
are user defined.  System defined labels may have a special meaning.
The user defined labels are in the AppInfo header.


Encryption strategies:

 * don't check any password
 * don't encrypt; check against system password
 * don't encrypt; check against category password
 * DES encryption with password
 * 3DES EDE encryption with password

We want to follow the Debian policy of not offering weak encryption:
if people don't use a reasonable strategy they don't get any
encryption.  For example we don't want to encrypt with a fixed key.

Whenever the master key changes or the strategy changes we may have to
unencrypt and reencrypt all the records in that category.

Perhaps optionally categories should require a password even to see
what records are in that category.

I haven't implemented any of this at the moment: it seems enough to
just use DES encryption and allow people to set an empty password if
they want that.



Storage of categories:
 
For each category, we want to store:
 
 - name of category
 - encryption strategy
 - timeout
 - other
 
This should go (I think) into the database's appinfo block, or at
least be referenced from there.
 
We want to have a way to check that the user enters the correct
password: if they make a typo it's much more friendly to just say
so than to try to decode the records and get garbage.
 
I think that's true.  Maybe showing garbage is cooler, but then the
record format will be damaged and in any case we don't want people
to be easily able to overwrite record unless they've entered the
right password.

However, we want to be careful not to compromise our encryption
scheme by doing this: it must not give away the password or allow a
known-plaintext attack.

Storing a secure hash of the password should be enough: we can hash
the entered password to check if it is correct.  If they match
correctly, we can go ahead and decrypt using that key.  Perhaps the
hash should contain some salt, so that attackers can't e.g. notice
that two categories have the same key?

Should we encrypt the records using the key itself?




----------------------------------------------------------------------
Password timeout:

The encryption key (AKA snib) is stored in a special memory block.
This block is owned by the operation system so it doesn't get removed
when the application is closed.  A feature entry points to it.

The expiry is implemented with AlmSetAlarm, which is available for all
supported operation system versions.  When the keyring application
receives an alarm it calls Snib_Eradicate, which clears the encryption
key and frees it.  The eradicate function is also called when the time
is changed.

All functions that ask for encryption key should clear their copy
after they are done with it.


----------------------------------------------------------------------
Encryption:

Calling the PalmOS functions is a good thing, because it makes the
code simpler and also probably makes it safe to re-export this code
from the USA.  This means we can only use DES and have to do a bit of
work to call it the right way, but that's OK.  

DES-EDE gives 2^112 possible encryption keys.  This is good enough,
though some algorithms allow larger keys.  However, since the only
secret here is the user's password it's the real limiting factor.

Reckon on about 6 bits of entropy per character, assuming they mix all
kinds of writable characters and avoid using pronounceable words.  To
get that many keys the user would have to enter a 20 character
password, which is asking a lot. 

So 3DES is probably quite sufficient -- it puts the likely weakest
link under the user's control.

I'm now encrypting records directly with a hash of the user's
password.  This hash is kept in memory when the program is unlocked,
and scribbled out when it's locked again (see above).  Actually, it
lasts even when the app exits and restarts, because we stay unlocked
then even if timeout hasn't expired.

We have to make sure the key and the hashed key are not stored
anywhere where they could be transferred to a PC.  So they can't go
into a preference or into the database.  

We leave the first part of the record -- the publicly-visible name --
unencrypted at the start.  This makes it easy to display and sort the
records even when they're locked.  We can even imagine a Global Find
implementation that works only over record names -- this might be
useful and reasonable.  Everything after that is encrypted.

This means we have to decrypt and re-encrypt all records when the user
changes their password.  That's pretty reasonable, for changing the
password ought to lock out anyone who knew the previous key.

We don't use the password itself as the key, but rather it's MD5 hash.
This gives 128 bits, so we have two 64-bit keys (though DES will
ignore the parity bits from each.)

It's supposed to be infeasible to derive this from the verification
hash.  I hope this is OK.

We will prompt for a password when creating a new database.  If the
user doesn't enter a password the database won't be created and he
leaves the application immediately.

The PalmOS encryption functions work between memory buffers.  This
gives us the mild inconvenience of needing to use two temporary
buffers: we have to pack/unpack records to give buffers for editing,
and have to use database manager functions to write out to the
database, rather than just writing into a buffer.  This is harmless.


Future Plans:

In the current scheme I can see several disadvantages: Every record is
encrypted with the same key so one may notice in the encrypted data
when two fields have the same account name.  Secondly the MD5 hash is
very fast and may lead to a brute force password attack.  The
encryption key doesn't depend on a salt.  If someone steals the
encryption key (from the snib) he can read every database with the
same master key.  And last but not least one cannot check from the
snib whether it matches the key database.

To solve all these issues I want to change to this key scheme:

Snib          = MD5(... MD5(MD5(MasterKey ; Salt) ; Salt ; MasterKey)
                    ... ; Salt ; MasterKey) [ iterated 1000 times ]
KeyHash       = Salt ; MD5(Snib ; Salt)
EncryptionKey = MD5(Snib)

Keyring only needs the Snib to check KeyHash or to encrypt a record.
Every records gets another key and the snib is dependent on the salt.

Also we should change from des-ecb to des-cbc.

An attacker can read the KeyHash.  Following attacks are possible:
 * Brute Forcing the MasterKey.  This is now much more infeasible
   because of the 1000 MD5 hashes that need to be calculated per try.
 * Brute Forcing the Snib.  Infeasible because the snib contains
   128 bit of randomness.
 * Reversing MD5.  This is commonly thought to be infeasible.
 * Dictionary attacks can't work because of the salt.
 * There may be problems due to the regularity of the iteration of the
   MD5 hash.  I believe there are no problems, though.



----------------------------------------------------------------------
Encryption in PalmOS:

Sample code:
    
    void KeyDB_StoreSessionKey(Char const *passwd, KeyringInfoPtr ki) {
        static const Byte src[8] = { 'm', 'a', 'r', 't', 'i', 'n', 0, 0 };
        static const Byte key[8] = { 0x42, 0, 0, 0, 0, 0, 0, 0 };
        Err err;
    
        err = EncDES((BytePtr) src, (BytePtr) key, ki->sessionKey, true);
    
        if (err)
    	App_ReportSysError("EncDES", err);
    }

On a PC, you can get the same result by

   openssl enc -des-ede-ecb -K KEYHEX -in foo.bin

where foo.bin contains the 8-byte text and KEYHEX is a hex
representation of the key, with the first byte first.

This is cool: it gives use some confidence that the algorithm is
implemented properly.  As far as I can see, if it's returning the same
results it must be the genuine DES algorithm.

So, it looks like our only option is DES-ECB: we could build something
stronger, but then Keyring would not be exportable from the US,
and I'd like to have that if it's at all possible. 

The PalmOS function only encrypts one block at a time, so we need to
either do block chaining ourselves or just use ECB mode.  Probably the
first is better if it's not too hard.

Since the records we're encrypting will be relatively small and since
code simplicity is somewhat important it seems OK to use DES-EDE-ECB
(as SSLeay and OpenSSL call it).


----------------------------------------------------------------------
Versioning

Palm apps are (apparently) allowed to get away with pretty spartan
support for backward and forward compatibility on the grounds of
keeping the app small.  The pigeon book suggests that the PC app do
that, but because our PC side probably won't be allowed to decode the
records this doesn't help much.  

Once we get past 1.0 we might consider storing the version in the
database or in a preference somewhere, and using it to convert.  If
the crypto stuff changes too much it may be hard to do the conversion,
however.


----------------------------------------------------------------------
Data leakage

It would be good to prevent secret data accumulating in the memory of
the handheld. 

The best solution is to scribble over buffers that have contained
secret data when we're done using them before they're returned to the
memory manager.

We will do OK in this respect by only writing encrypted data into the
long-lived database memory.  Although unencrypted secret data may
exist in the data heap it's much quite likely to be overwritten soon by
other applications, the OS, or by a soft reset than data in the
database.  This is not a guarantee.

The main exposure that's out of our control is the buffers allocated
for editing in the form.  

Without the PalmOS source code we can't know whether it will allocate
new buffers, resize them, make copies or anything else.  However,
trusting that it will be lazy we can assume:

 * it won't copy the data anywhere else, except when the buffers need
   to be grown.

 * the buffers won't shrink

We do need to make sure to scribble over the buffers when the form
goes away rather than just letting the form fields dispose of their
own memory.  At the moment this is only done with the master password.

If the user chooses to copy text to the clipboard that's their own
problem. 

 LocalWords:  KeyringInfo strz ULONG record's KeyRecordType unencrypted NUL ECB
 LocalWords:  DES Debian unencrypt reencrypt appinfo AlmSetAlarm keyring PalmOS
 LocalWords:  app apps EncDES SSLeay OpenSSL Versioning handheld
