From: simon Date: Sat, 22 Sep 2001 20:52:21 +0000 (+0000) Subject: Add support for DSA authentication in SSH2, following clever ideas X-Git-Url: https://git.distorted.org.uk/u/mdw/putty/commitdiff_plain/5c72ca6161da0e7976245222c412d62ebae2e386 Add support for DSA authentication in SSH2, following clever ideas on how to get round the problem of generating a good k. git-svn-id: svn://svn.tartarus.org/sgt/putty@1284 cda61777-01e9-0310-a592-d414129be87e --- diff --git a/Makefile b/Makefile index 70c34e3d..8f5bbd71 100644 --- a/Makefile +++ b/Makefile @@ -104,16 +104,16 @@ MOBJ2 = tree234.$(OBJ) OBJS1 = sshcrc.$(OBJ) sshdes.$(OBJ) sshmd5.$(OBJ) sshrsa.$(OBJ) sshrand.$(OBJ) OBJS2 = sshsha.$(OBJ) sshblowf.$(OBJ) noise.$(OBJ) sshdh.$(OBJ) sshdss.$(OBJ) OBJS3 = sshbn.$(OBJ) sshpubk.$(OBJ) ssh.$(OBJ) pageantc.$(OBJ) sshzlib.$(OBJ) -OBJS4 = x11fwd.$(OBJ) portfwd.$(OBJ) sshaes.$(OBJ) +OBJS4 = x11fwd.$(OBJ) portfwd.$(OBJ) sshaes.$(OBJ) sshsh512.$(OBJ) ##-- objects pageant PAGE1 = pageant.$(OBJ) sshrsa.$(OBJ) sshpubk.$(OBJ) sshdes.$(OBJ) sshbn.$(OBJ) PAGE2 = sshmd5.$(OBJ) version.$(OBJ) tree234.$(OBJ) misc.$(OBJ) sshaes.$(OBJ) -PAGE3 = sshsha.$(OBJ) pageantc.$(OBJ) +PAGE3 = sshsha.$(OBJ) pageantc.$(OBJ) sshdss.$(OBJ) sshsh512.$(OBJ) ##-- objects puttygen -GEN1 = puttygen.$(OBJ) sshrsag.$(OBJ) sshprime.$(OBJ) sshdes.$(OBJ) -GEN2 = sshbn.$(OBJ) sshmd5.$(OBJ) version.$(OBJ) sshrand.$(OBJ) noise.$(OBJ) -GEN3 = sshsha.$(OBJ) winstore.$(OBJ) misc.$(OBJ) winctrls.$(OBJ) -GEN4 = sshrsa.$(OBJ) sshpubk.$(OBJ) sshaes.$(OBJ) +GEN1 = puttygen.$(OBJ) sshrsag.$(OBJ) sshdssg.$(OBJ) sshprime.$(OBJ) +GEN2 = sshdes.$(OBJ) sshbn.$(OBJ) sshmd5.$(OBJ) version.$(OBJ) sshrand.$(OBJ) +GEN3 = noise.$(OBJ) sshsha.$(OBJ) winstore.$(OBJ) misc.$(OBJ) winctrls.$(OBJ) +GEN4 = sshrsa.$(OBJ) sshdss.$(OBJ) sshpubk.$(OBJ) sshaes.$(OBJ) sshsh512.$(OBJ) ##-- resources putty puttytel PRESRC = win_res.$(RES) ##-- resources pageant @@ -273,57 +273,60 @@ plink.rsp: makefile be_all.$(OBJ): be_all.c network.h misc.h puttymem.h putty.h be_none.$(OBJ): be_none.c network.h misc.h puttymem.h putty.h be_nossh.$(OBJ): be_nossh.c network.h misc.h puttymem.h putty.h -ber.$(OBJ): ber.c network.h asn.h misc.h asnerror.h puttymem.h ssh.h putty.h +ber.$(OBJ): ber.c network.h asn.h misc.h asnerror.h int64.h puttymem.h ssh.h putty.h cert.$(OBJ): cert.c asn.h asnerror.h misc.h puttymem.h cert.h crypto.h +debug.$(OBJ): debug.c debug.h int64.$(OBJ): int64.c int64.h ldisc.$(OBJ): ldisc.c network.h misc.h puttymem.h putty.h misc.$(OBJ): misc.c network.h misc.h puttymem.h putty.h -mscrypto.$(OBJ): mscrypto.c network.h puttymem.h ssh.h +mscrypto.$(OBJ): mscrypto.c network.h int64.h puttymem.h ssh.h no_ssl.$(OBJ): no_ssl.c network.h misc.h puttymem.h putty.h -noise.$(OBJ): noise.c network.h misc.h puttymem.h storage.h ssh.h putty.h -pageant.$(OBJ): pageant.c network.h puttymem.h ssh.h tree234.h +noise.$(OBJ): noise.c network.h misc.h puttymem.h storage.h int64.h ssh.h putty.h +pageant.$(OBJ): pageant.c network.h int64.h puttymem.h ssh.h tree234.h pageantc.$(OBJ): pageantc.c puttymem.h plink.$(OBJ): plink.c network.h misc.h puttymem.h storage.h putty.h tree234.h -portfwd.$(OBJ): portfwd.c network.h misc.h puttymem.h ssh.h putty.h +portfwd.$(OBJ): portfwd.c network.h misc.h int64.h puttymem.h ssh.h putty.h psftp.$(OBJ): psftp.c network.h misc.h sftp.h ssh.h storage.h int64.h puttymem.h putty.h -puttygen.$(OBJ): puttygen.c network.h misc.h puttymem.h winstuff.h ssh.h putty.h +puttygen.$(OBJ): puttygen.c network.h misc.h int64.h puttymem.h winstuff.h ssh.h putty.h raw.$(OBJ): raw.c network.h misc.h puttymem.h putty.h rlogin.$(OBJ): rlogin.c network.h misc.h puttymem.h putty.h scp.$(OBJ): scp.c network.h misc.h sftp.h ssh.h storage.h puttymem.h int64.h putty.h winstuff.h settings.$(OBJ): settings.c network.h misc.h puttymem.h storage.h putty.h sftp.$(OBJ): sftp.c sftp.h int64.h sizetip.$(OBJ): sizetip.c network.h misc.h puttymem.h winstuff.h putty.h -ssh.$(OBJ): ssh.c network.h misc.h puttymem.h ssh.h putty.h tree234.h -sshaes.$(OBJ): sshaes.c network.h puttymem.h ssh.h -sshblowf.$(OBJ): sshblowf.c network.h puttymem.h ssh.h -sshbn.$(OBJ): sshbn.c network.h misc.h puttymem.h ssh.h putty.h +ssh.$(OBJ): ssh.c network.h misc.h int64.h puttymem.h ssh.h putty.h tree234.h +sshaes.$(OBJ): sshaes.c network.h int64.h puttymem.h ssh.h +sshblowf.$(OBJ): sshblowf.c network.h int64.h puttymem.h ssh.h +sshbn.$(OBJ): sshbn.c network.h misc.h int64.h puttymem.h ssh.h putty.h sshcrc.$(OBJ): sshcrc.c -sshdes.$(OBJ): sshdes.c network.h puttymem.h ssh.h -sshdh.$(OBJ): sshdh.c network.h puttymem.h ssh.h -sshdss.$(OBJ): sshdss.c network.h puttymem.h ssh.h -sshmd5.$(OBJ): sshmd5.c network.h puttymem.h ssh.h -sshprime.$(OBJ): sshprime.c network.h puttymem.h ssh.h -sshpubk.$(OBJ): sshpubk.c network.h puttymem.h ssh.h -sshrand.$(OBJ): sshrand.c network.h puttymem.h ssh.h -sshrsa.$(OBJ): sshrsa.c network.h puttymem.h ssh.h -sshrsag.$(OBJ): sshrsag.c network.h puttymem.h ssh.h -sshsha.$(OBJ): sshsha.c network.h puttymem.h ssh.h -sshzlib.$(OBJ): sshzlib.c network.h puttymem.h ssh.h +sshdes.$(OBJ): sshdes.c network.h int64.h puttymem.h ssh.h +sshdh.$(OBJ): sshdh.c network.h int64.h puttymem.h ssh.h +sshdss.$(OBJ): sshdss.c network.h misc.h int64.h puttymem.h ssh.h +sshdssg.$(OBJ): sshdssg.c network.h misc.h int64.h puttymem.h ssh.h +sshmd5.$(OBJ): sshmd5.c network.h int64.h puttymem.h ssh.h +sshprime.$(OBJ): sshprime.c network.h int64.h puttymem.h ssh.h +sshpubk.$(OBJ): sshpubk.c network.h int64.h puttymem.h ssh.h +sshrand.$(OBJ): sshrand.c network.h int64.h puttymem.h ssh.h +sshrsa.$(OBJ): sshrsa.c network.h int64.h puttymem.h ssh.h +sshrsag.$(OBJ): sshrsag.c network.h int64.h puttymem.h ssh.h +sshsh512.$(OBJ): sshsh512.c network.h int64.h puttymem.h ssh.h +sshsha.$(OBJ): sshsha.c network.h int64.h puttymem.h ssh.h +sshzlib.$(OBJ): sshzlib.c network.h int64.h puttymem.h ssh.h ssl.$(OBJ): ssl.c network.h asnerror.h misc.h cert.h crypto.h ssl.h int64.h puttymem.h telnet.$(OBJ): telnet.c network.h misc.h puttymem.h putty.h terminal.$(OBJ): terminal.c network.h misc.h puttymem.h putty.h tree234.h -test.$(OBJ): test.c network.h puttymem.h ssh.h +test.$(OBJ): test.c network.h int64.h puttymem.h ssh.h tree234.$(OBJ): tree234.c tree234.h unicode.$(OBJ): unicode.c network.h misc.h puttymem.h putty.h version.$(OBJ): version.c wcwidth.$(OBJ): wcwidth.c wildcard.$(OBJ): wildcard.c winctrls.$(OBJ): winctrls.c network.h misc.h puttymem.h putty.h winstuff.h -windlg.$(OBJ): windlg.c network.h misc.h ssh.h storage.h puttymem.h putty.h winstuff.h win_res.h +windlg.$(OBJ): windlg.c network.h misc.h ssh.h storage.h puttymem.h int64.h putty.h winstuff.h win_res.h window.$(OBJ): window.c network.h misc.h puttymem.h storage.h winstuff.h putty.h win_res.h winnet.$(OBJ): winnet.c network.h misc.h puttymem.h putty.h tree234.h winstore.$(OBJ): winstore.c network.h misc.h puttymem.h storage.h putty.h -x11fwd.$(OBJ): x11fwd.c network.h misc.h puttymem.h ssh.h putty.h +x11fwd.$(OBJ): x11fwd.c network.h misc.h int64.h puttymem.h ssh.h putty.h ##-- # Hack to force version.obj to be rebuilt always diff --git a/doc/pubkey.but b/doc/pubkey.but index 6946fa96..fccd7b0d 100644 --- a/doc/pubkey.but +++ b/doc/pubkey.but @@ -1,4 +1,4 @@ -\versionid $Id: pubkey.but,v 1.4 2001/09/22 15:36:44 simon Exp $ +\versionid $Id: pubkey.but,v 1.5 2001/09/22 20:52:21 simon Exp $ \# FIXME: passphrases, examples (e.g what does a key for pasting into \# authorized_keys look like?), index entries, links. @@ -59,7 +59,37 @@ shuts down, without ever having stored your decrypted private key on disk. Many people feel this is a good compromise between security and convenience. See \k{pageant} for further details. -\H{pubkey-puttygen} PuTTYgen: RSA key generator for PuTTY +\S{pubkey-types} Different types of public key + +The PuTTY key generator, described in \k{pubkey-puttygen}, offers +you the opportunity to generate several types of key pair: + +\b An RSA key for use with the SSH 1 protocol. +\b An RSA key for use with the SSH 2 protocol. +\b A DSA key for use with the SSH 2 protocol. + +The SSH 1 protocol only supports RSA keys; if you will be connecting +using the SSH 1 protocol, you must select the first key type or your +key will be completely useless. + +SSH 2 supports more than one key type. The two types supported by +PuTTY are RSA and DSA. + +The PuTTY developers \e{strongly} recommend you use RSA. DSA has an +intrinsic weakness which makes it very easy to create a signature +which contains enough information to give away the \e{private} key! +This would allow an attacker to pretend to be you for any number of +future sessions. PuTTY's implementation has taken very careful +precautions to avoid this weakness, but we cannot be 100% certain we +have managed it, and if you have the choice we strongly recommend +using RSA keys instead. + +If you really need to connect to an SSH server which only supports +DSA, then you probably have no choice but to use DSA. If you do use +DSA, we recommend you do not use the same key to authenticate with +more than one server. + +\H{pubkey-puttygen} PuTTYgen: Key generator for PuTTY PuTTYgen is a key generator. It generates pairs of public and private keys to be used with PuTTY, PSCP, and Plink, as well as the PuTTY @@ -73,8 +103,9 @@ existing private key. \S{pubkey-puttygen-generate} Generate a new key Before generating a new key you have to choose the strength of the -encryption. With \e{Parameters} you define the strength of the key. The -default of 1024 should be OK for most users. +encryption, and the type of the key (see \k{pubkey-types}). With +\e{Parameters} you define the strength of the key. The default of +1024 should be OK for most users. Pressing the \e{Generate} button starts the process of generating a new key pair. You then have to move the mouse over the blank area in @@ -116,16 +147,36 @@ private key this way. Just modify the values and \e{Save} the key. Connect to your SSH server using PuTTY with the SSH protocol. When the connection succeeds you will be prompted for your user name and -password to login. Once logged in change into the \c{.ssh} directory -and open the file \c{authorized_keys} with your favorite editor (you -may have to create this file if this is the first key to add). - -Switch to the PuTTYgen window and select all of the content below -\e{Public key for pasting into authorized_keys file}, copy it to the -clipboard (\c{Ctrl+C}). Then, switch back to the PuTTY window and -insert the data into the open file. Save the file. - -From now on you can use the private key for authentication to this -host. Either select the private key in PuTTY's \e{Connection}, -\e{SSH} panel: \e{Private key file for authentication} dialog or use -it with Pageant as described in \k{pageant}. +password to login. Once logged in, you must configure the server to +accept your public key for authentication: + +\b If your server is using the SSH 1 protocol, you should change +into the \c{.ssh} directory and open the file \c{authorized_keys} +with your favorite editor. (You may have to create this file if this +is the first key you have put in it). Then switch to the PuTTYgen +window, select all of the text in the \e{Public key for pasting into +authorized_keys file} box, and copy it to the clipboard +(\c{Ctrl+C}). Then, switch back to the PuTTY window and insert the +data into the open file, making sure it ends up all on one line. +Save the file. + +\b If your server is OpenSSH and is using the SSH 2 protocol, you +should follow the same instructions except that the file will be +called \c{authorized_keys2}. + +\b If your server is \cw{ssh.com}'s SSH 2 product, you need to save +a \e{public} key file from PuTTYgen, and copy that into the +\c{.ssh2} directory on the server. Then you should go into that +\c{.ssh2} directory, and edit (or create) a file called +\c{authorization}. In this file you should put a line like \c{Key +mykey.pub}, with \c{mykey.pub} replaced by the name of your key +file. + +\b For other SSH server software, you should refer to the manual for +that server. + +From now on you should be able to use the private key for +authentication to this host. Either select the private key in +PuTTY's \e{Connection}, \e{SSH} panel: \e{Private key file for +authentication} dialog or use it with Pageant as described in +\k{pageant}. diff --git a/pageant.c b/pageant.c index 6ab373e1..a7efcada 100644 --- a/pageant.c +++ b/pageant.c @@ -65,7 +65,7 @@ int agent_exists(void); * pads its data with random bytes. Since we only use rsadecrypt() * and the signing functions, which are deterministic, this should * never be called. - * + * * If it _is_ called, there is a _serious_ problem, because it * won't generate true random numbers. So we must scream, panic, * and exit immediately if that should happen. @@ -613,7 +613,7 @@ static void answer_msg(void *msg) break; case SSH2_AGENTC_SIGN_REQUEST: /* - * Reply with either SSH2_AGENT_RSA_RESPONSE or + * Reply with either SSH2_AGENT_SIGN_RESPONSE or * SSH_AGENT_FAILURE, depending on whether we have that key * or not. */ @@ -696,6 +696,8 @@ static void answer_msg(void *msg) /* Add further algorithm names here. */ if (alglen == 7 && !memcmp(alg, "ssh-rsa", 7)) key->alg = &ssh_rsa; + else if (alglen == 7 && !memcmp(alg, "ssh-dss", 7)) + key->alg = &ssh_dss; else { sfree(key); goto failure; diff --git a/puttygen.c b/puttygen.c index 12699685..7c3ef0d6 100644 --- a/puttygen.c +++ b/puttygen.c @@ -21,72 +21,72 @@ /* ---------------------------------------------------------------------- * Progress report code. This is really horrible :-) */ -#define PHASE1TOTAL 0x10000 -#define PHASE2TOTAL 0x10000 -#define PHASE3TOTAL 0x04000 -#define PHASE1START 0 -#define PHASE2START (PHASE1TOTAL) -#define PHASE3START (PHASE1TOTAL + PHASE2TOTAL) -#define TOTALTOTAL (PHASE1TOTAL + PHASE2TOTAL + PHASE3TOTAL) -#define PROGRESSBIGRANGE 65535 -#define DIVISOR ((TOTALTOTAL + PROGRESSBIGRANGE - 1) / PROGRESSBIGRANGE) -#define PROGRESSRANGE (TOTALTOTAL / DIVISOR) +#define PROGRESSRANGE 65535 +#define MAXPHASE 5 struct progress { - unsigned phase1param, phase1current, phase1n; - unsigned phase2param, phase2current, phase2n; - unsigned phase3mult; + int nphases; + struct { + int exponential; + unsigned startpoint, total; + unsigned param, current, n; /* if exponential */ + unsigned mult; /* if linear */ + } phases[MAXPHASE]; + unsigned total, divisor, range; HWND progbar; }; -static void progress_update(void *param, int phase, int iprogress) +static void progress_update(void *param, int action, int phase, int iprogress) { struct progress *p = (struct progress *) param; unsigned progress = iprogress; int position; - switch (phase) { - case -1: - p->phase1param = 0x10000 + progress; - p->phase1current = 0x10000; - p->phase1n = 0; - return; - case -2: - p->phase2param = 0x10000 + progress; - p->phase2current = 0x10000; - p->phase2n = 0; - return; - case -3: - p->phase3mult = PHASE3TOTAL / progress; - return; - case 1: - while (p->phase1n < progress) { - p->phase1n++; - p->phase1current *= p->phase1param; - p->phase1current /= 0x10000; - } - position = PHASE1START + 0x10000 - p->phase1current; + if (action < PROGFN_READY && p->nphases < phase) + p->nphases = phase; + switch (action) { + case PROGFN_LIN_PHASE: + p->phases[phase-1].exponential = 0; + p->phases[phase-1].mult = p->phases[phase].total / progress; + break; + case PROGFN_EXP_PHASE: + p->phases[phase-1].exponential = 1; + p->phases[phase-1].param = 0x10000 + progress; + p->phases[phase-1].current = p->phases[phase-1].total; + p->phases[phase-1].n = 0; break; - case 2: - while (p->phase2n < progress) { - p->phase2n++; - p->phase2current *= p->phase2param; - p->phase2current /= 0x10000; + case PROGFN_PHASE_EXTENT: + p->phases[phase-1].total = progress; + break; + case PROGFN_READY: + { + unsigned total = 0; + int i; + for (i = 0; i < p->nphases; i++) { + p->phases[i].startpoint = total; + total += p->phases[i].total; + } + p->total = total; + p->divisor = ((p->total + PROGRESSRANGE - 1) / PROGRESSRANGE); + p->range = p->total / p->divisor; + SendMessage(p->progbar, PBM_SETRANGE, 0, MAKELPARAM(0, p->range)); } - position = PHASE2START + 0x10000 - p->phase2current; break; - case 3: - position = PHASE3START + progress * p->phase3mult; + case PROGFN_PROGRESS: + if (p->phases[phase-1].exponential) { + while (p->phases[phase-1].n < progress) { + p->phases[phase-1].n++; + p->phases[phase-1].current *= p->phases[phase-1].param; + p->phases[phase-1].current /= 0x10000; + } + position = (p->phases[phase-1].startpoint + + p->phases[phase-1].total - p->phases[phase-1].current); + } else { + position = (p->phases[phase-1].startpoint + + progress * p->phases[phase-1].mult); + } + SendMessage(p->progbar, PBM_SETPOS, position / p->divisor, 0); break; - default: - /* - * Shouldn't happen, but having a default clause placates - * gcc -Wall, which would otherwise complain that - * `position' might be used uninitialised. - */ - return; } - - SendMessage(p->progbar, PBM_SETPOS, position / DIVISOR, 0); } extern char ver[]; @@ -291,7 +291,9 @@ struct rsa_key_thread_params { HWND progressbar; /* notify this with progress */ HWND dialog; /* notify this on completion */ int keysize; /* bits in key */ + int is_dsa; struct RSAKey *key; + struct dss_key *dsskey; }; static DWORD WINAPI generate_rsa_key_thread(void *param) { @@ -300,7 +302,10 @@ static DWORD WINAPI generate_rsa_key_thread(void *param) struct progress prog; prog.progbar = params->progressbar; - rsa_generate(params->key, params->keysize, progress_update, &prog); + if (params->is_dsa) + dsa_generate(params->dsskey, params->keysize, progress_update, &prog); + else + rsa_generate(params->key, params->keysize, progress_update, &prog); PostMessage(params->dialog, WM_DONEKEY, 0, 0); @@ -314,11 +319,12 @@ struct MainDlgState { int key_exists; int entropy_got, entropy_required, entropy_size; int keysize; - int ssh2; + int ssh2, is_dsa; char **commentptr; /* points to key.comment or ssh2key.comment */ struct ssh2_userkey ssh2key; unsigned *entropy; struct RSAKey key; + struct dss_key dsskey; }; static void hidemany(HWND hwnd, const int *ids, int hideit) @@ -465,7 +471,7 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, IDC_LOADSTATIC, IDC_LOAD, IDC_SAVESTATIC, IDC_SAVE, IDC_SAVEPUB, IDC_BOX_PARAMS, - IDC_TYPESTATIC, IDC_KEYSSH1, IDC_KEYSSH2RSA, + IDC_TYPESTATIC, IDC_KEYSSH1, IDC_KEYSSH2RSA, IDC_KEYSSH2DSA, IDC_BITSSTATIC, IDC_BITS, IDC_ABOUT, }; @@ -511,7 +517,7 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, { struct ctlpos cp, cp2; - /* Accelerators used: acglops1rb */ + /* Accelerators used: acglops1rbd */ ctlposinit(&cp, hwnd, 10, 10, 10); bartitle(&cp, "Public and private key generation for PuTTY", @@ -547,9 +553,10 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, "&Save private key", IDC_SAVE); endbox(&cp); beginbox(&cp, "Parameters", IDC_BOX_PARAMS); - radioline(&cp, "Type of key to generate:", IDC_TYPESTATIC, 2, + radioline(&cp, "Type of key to generate:", IDC_TYPESTATIC, 3, "SSH&1 (RSA)", IDC_KEYSSH1, - "SSH2 &RSA", IDC_KEYSSH2RSA, NULL); + "SSH2 &RSA", IDC_KEYSSH2RSA, + "SSH2 &DSA", IDC_KEYSSH2DSA, NULL); staticedit(&cp, "Number of &bits in a generated key:", IDC_BITSSTATIC, IDC_BITS, 20); endbox(&cp); @@ -599,7 +606,9 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, params->progressbar = GetDlgItem(hwnd, IDC_PROGRESS); params->dialog = hwnd; params->keysize = state->keysize; + params->is_dsa = state->is_dsa; params->key = &state->key; + params->dsskey = &state->dsskey; if (!CreateThread(NULL, 0, generate_rsa_key_thread, params, 0, &threadid)) { @@ -652,6 +661,7 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, state->keysize = DEFAULT_KEYSIZE; /* If we ever introduce a new key type, check it here! */ state->ssh2 = !IsDlgButtonChecked(hwnd, IDC_KEYSSH1); + state->is_dsa = IsDlgButtonChecked(hwnd, IDC_KEYSSH2DSA); if (state->keysize < 256) { int ret = MessageBox(hwnd, "PuTTYgen will not generate a key" @@ -937,8 +947,9 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, state = (struct MainDlgState *) GetWindowLong(hwnd, GWL_USERDATA); state->generation_thread_exists = FALSE; state->key_exists = TRUE; - SendDlgItemMessage(hwnd, IDC_PROGRESS, PBM_SETPOS, PROGRESSRANGE, - 0); + SendDlgItemMessage(hwnd, IDC_PROGRESS, PBM_SETRANGE, 0, + MAKELPARAM(0, PROGRESSRANGE)); + SendDlgItemMessage(hwnd, IDC_PROGRESS, PBM_SETPOS, PROGRESSRANGE, 0); EnableWindow(GetDlgItem(hwnd, IDC_GENERATE), 1); EnableWindow(GetDlgItem(hwnd, IDC_LOAD), 1); EnableWindow(GetDlgItem(hwnd, IDC_SAVE), 1); @@ -947,8 +958,13 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, EnableWindow(GetDlgItem(hwnd, IDC_KEYSSH2RSA), 1); EnableWindow(GetDlgItem(hwnd, IDC_BITS), 1); if (state->ssh2) { - state->ssh2key.data = &state->key; - state->ssh2key.alg = &ssh_rsa; + if (state->is_dsa) { + state->ssh2key.data = &state->dsskey; + state->ssh2key.alg = &ssh_dss; + } else { + state->ssh2key.data = &state->key; + state->ssh2key.alg = &ssh_rsa; + } state->commentptr = &state->ssh2key.comment; } else { state->commentptr = &state->key.comment; @@ -965,7 +981,10 @@ static int CALLBACK MainDlgProc(HWND hwnd, UINT msg, struct tm *tm; time(&t); tm = localtime(&t); - strftime(*state->commentptr, 30, "rsa-key-%Y%m%d", tm); + if (state->is_dsa) + strftime(*state->commentptr, 30, "dsa-key-%Y%m%d", tm); + else + strftime(*state->commentptr, 30, "rsa-key-%Y%m%d", tm); } /* diff --git a/ssh.h b/ssh.h index 2406bd63..0d9613b0 100644 --- a/ssh.h +++ b/ssh.h @@ -2,6 +2,7 @@ #include "puttymem.h" #include "network.h" +#include "int64.h" struct ssh_channel; @@ -48,6 +49,10 @@ struct RSAKey { char *comment; }; +struct dss_key { + Bignum p, q, g, y, x; +}; + int makekey(unsigned char *data, struct RSAKey *result, unsigned char **keystr, int order); int makeprivate(unsigned char *data, struct RSAKey *result); @@ -92,12 +97,25 @@ typedef struct { int blkused; uint32 lenhi, lenlo; } SHA_State; - void SHA_Init(SHA_State * s); void SHA_Bytes(SHA_State * s, void *p, int len); void SHA_Final(SHA_State * s, unsigned char *output); void SHA_Simple(void *p, int len, unsigned char *output); +void hmac_sha1_simple(void *key, int keylen, void *data, int datalen, + unsigned char *output); + +typedef struct { + uint64 h[8]; + unsigned char block[128]; + int blkused; + uint32 len[4]; +} SHA512_State; +void SHA512_Init(SHA512_State * s); +void SHA512_Bytes(SHA512_State * s, const void *p, int len); +void SHA512_Final(SHA512_State * s, unsigned char *output); +void SHA512_Simple(const void *p, int len, unsigned char *output); + struct ssh_cipher { void (*sesskey) (unsigned char *key); /* for ssh 1 */ void (*encrypt) (unsigned char *blk, int len); @@ -219,7 +237,7 @@ void ssh_send_port_open(void *channel, char *hostname, int port, char *org); Bignum copybn(Bignum b); Bignum bn_power_2(int n); void bn_restore_invariant(Bignum b); -Bignum bignum_from_short(unsigned short n); +Bignum bignum_from_long(unsigned long n); void freebn(Bignum b); Bignum modpow(Bignum base, Bignum exp, Bignum mod); Bignum modmul(Bignum a, Bignum b, Bignum mod); @@ -238,6 +256,9 @@ Bignum biggcd(Bignum a, Bignum b); unsigned short bignum_mod_short(Bignum number, unsigned short modulus); Bignum bignum_add_long(Bignum number, unsigned long addend); Bignum bigmul(Bignum a, Bignum b); +Bignum bigmuladd(Bignum a, Bignum b, Bignum addend); +Bignum bigdiv(Bignum a, Bignum b); +Bignum bigmod(Bignum a, Bignum b); Bignum modinv(Bignum number, Bignum modulus); Bignum bignum_bitmask(Bignum number); Bignum bignum_rshift(Bignum number, int shift); @@ -280,12 +301,19 @@ void aes256_decrypt_pubkey(unsigned char *key, unsigned char *blk, /* * For progress updates in the key generation utility. */ -typedef void (*progfn_t) (void *param, int phase, int progress); +#define PROGFN_LIN_PHASE 1 +#define PROGFN_EXP_PHASE 2 +#define PROGFN_PHASE_EXTENT 3 +#define PROGFN_READY 4 +#define PROGFN_PROGRESS 5 +typedef void (*progfn_t) (void *param, int action, int phase, int progress); int rsa_generate(struct RSAKey *key, int bits, progfn_t pfn, void *pfnparam); -Bignum primegen(int bits, int modulus, int residue, int phase, - progfn_t pfn, void *pfnparam); +int dsa_generate(struct dss_key *key, int bits, progfn_t pfn, + void *pfnparam); +Bignum primegen(int bits, int modulus, int residue, Bignum factor, + int phase, progfn_t pfn, void *pfnparam); /* diff --git a/sshbn.c b/sshbn.c index 0d0fce34..505a66c3 100644 --- a/sshbn.c +++ b/sshbn.c @@ -6,13 +6,7 @@ #include #include -#if 0 // use PuTTY main debugging for diagbn() -#include -#include "putty.h" -#define debugprint debug -#else -#define debugprint(x) printf x -#endif +#include "misc.h" #define BIGNUM_INTERNAL typedef unsigned short *Bignum; @@ -409,9 +403,10 @@ Bignum modmul(Bignum p, Bignum q, Bignum mod) * Compute p % mod. * The most significant word of mod MUST be non-zero. * We assume that the result array is the same size as the mod array. - * We optionally write out a quotient. + * We optionally write out a quotient if `quotient' is non-NULL. + * We can avoid writing out the result if `result' is NULL. */ -void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient) +void bigdivmod(Bignum p, Bignum mod, Bignum result, Bignum quotient) { unsigned short *n, *m; int mshift; @@ -460,9 +455,11 @@ void bigmod(Bignum p, Bignum mod, Bignum result, Bignum quotient) } /* Copy result to buffer */ - for (i = 1; i <= result[0]; i++) { - int j = plen - i; - result[i] = j >= 0 ? n[j] : 0; + if (result) { + for (i = 1; i <= result[0]; i++) { + int j = plen - i; + result[i] = j >= 0 ? n[j] : 0; + } } /* Free temporary arrays */ @@ -749,16 +746,17 @@ Bignum bignum_bitmask(Bignum n) } /* - * Convert a (max 16-bit) short into a bignum. + * Convert a (max 32-bit) long into a bignum. */ -Bignum bignum_from_short(unsigned short n) +Bignum bignum_from_long(unsigned long n) { Bignum ret; - ret = newbn(2); + ret = newbn(3); ret[1] = n & 0xFFFF; ret[2] = (n >> 16) & 0xFFFF; - ret[0] = (ret[2] ? 2 : 1); + ret[3] = 0; + ret[0] = (ret[2] ? 2 : 1); return ret; } @@ -804,21 +802,40 @@ void diagbn(char *prefix, Bignum md) int i, nibbles, morenibbles; static const char hex[] = "0123456789ABCDEF"; - debugprint(("%s0x", prefix ? prefix : "")); + debug(("%s0x", prefix ? prefix : "")); nibbles = (3 + bignum_bitcount(md)) / 4; if (nibbles < 1) nibbles = 1; morenibbles = 4 * md[0] - nibbles; for (i = 0; i < morenibbles; i++) - debugprint(("-")); + debug(("-")); for (i = nibbles; i--;) - debugprint( - ("%c", - hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF])); + debug(("%c", + hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF])); if (prefix) - debugprint(("\n")); + debug(("\n")); +} + +/* + * Simple division. + */ +Bignum bigdiv(Bignum a, Bignum b) +{ + Bignum q = newbn(a[0]); + bigdivmod(a, b, NULL, q); + return q; +} + +/* + * Simple remainder. + */ +Bignum bigmod(Bignum a, Bignum b) +{ + Bignum r = newbn(b[0]); + bigdivmod(a, b, r, NULL); + return r; } /* @@ -829,12 +846,9 @@ Bignum biggcd(Bignum av, Bignum bv) Bignum a = copybn(av); Bignum b = copybn(bv); - diagbn("a = ", a); - diagbn("b = ", b); while (bignum_cmp(b, Zero) != 0) { Bignum t = newbn(b[0]); - bigmod(a, b, t, NULL); - diagbn("t = ", t); + bigdivmod(a, b, t, NULL); while (t[0] > 1 && t[t[0]] == 0) t[0]--; freebn(a); @@ -860,7 +874,7 @@ Bignum modinv(Bignum number, Bignum modulus) while (bignum_cmp(b, One) != 0) { Bignum t = newbn(b[0]); Bignum q = newbn(a[0]); - bigmod(a, b, t, q); + bigdivmod(a, b, t, q); while (t[0] > 1 && t[t[0]] == 0) t[0]--; freebn(a); diff --git a/sshdss.c b/sshdss.c index 71ad59e1..b2179a83 100644 --- a/sshdss.c +++ b/sshdss.c @@ -3,6 +3,7 @@ #include #include "ssh.h" +#include "misc.h" #define GET_32BIT(cp) \ (((unsigned long)(unsigned char)(cp)[0] << 24) | \ @@ -16,11 +17,35 @@ (cp)[2] = (unsigned char)((value) >> 8); \ (cp)[3] = (unsigned char)(value); } -#if 0 -#define DEBUG_DSS -#else -#define diagbn(x,y) -#endif +static void sha_mpint(SHA_State * s, Bignum b) +{ + unsigned char *p; + unsigned char lenbuf[4]; + int len; + len = (bignum_bitcount(b) + 8) / 8; + PUT_32BIT(lenbuf, len); + SHA_Bytes(s, lenbuf, 4); + while (len-- > 0) { + lenbuf[0] = bignum_byte(b, len); + SHA_Bytes(s, lenbuf, 1); + } + memset(lenbuf, 0, sizeof(lenbuf)); +} + +static void sha512_mpint(SHA512_State * s, Bignum b) +{ + unsigned char *p; + unsigned char lenbuf[4]; + int len; + len = (bignum_bitcount(b) + 8) / 8; + PUT_32BIT(lenbuf, len); + SHA512_Bytes(s, lenbuf, 4); + while (len-- > 0) { + lenbuf[0] = bignum_byte(b, len); + SHA512_Bytes(s, lenbuf, 1); + } + memset(lenbuf, 0, sizeof(lenbuf)); +} static void getstring(char **data, int *datalen, char **p, int *length) { @@ -62,10 +87,6 @@ static Bignum get160(char **data, int *datalen) return b; } -struct dss_key { - Bignum p, q, g, y; -}; - static void *dss_newkey(char *data, int len) { char *p; @@ -236,14 +257,8 @@ static int dss_verifysig(void *key, char *sig, int siglen, } sig += 4, siglen -= 4; /* skip yet another length field */ } - diagbn("p=", dss->p); - diagbn("q=", dss->q); - diagbn("g=", dss->g); - diagbn("y=", dss->y); r = get160(&sig, &siglen); - diagbn("r=", r); s = get160(&sig, &siglen); - diagbn("s=", s); if (!r || !s) return 0; @@ -251,7 +266,6 @@ static int dss_verifysig(void *key, char *sig, int siglen, * Step 1. w <- s^-1 mod q. */ w = modinv(s, dss->q); - diagbn("w=", w); /* * Step 2. u1 <- SHA(message) * w mod q. @@ -260,28 +274,20 @@ static int dss_verifysig(void *key, char *sig, int siglen, p = hash; slen = 20; sha = get160(&p, &slen); - diagbn("sha=", sha); u1 = modmul(sha, w, dss->q); - diagbn("u1=", u1); /* * Step 3. u2 <- r * w mod q. */ u2 = modmul(r, w, dss->q); - diagbn("u2=", u2); /* * Step 4. v <- (g^u1 * y^u2 mod p) mod q. */ gu1p = modpow(dss->g, u1, dss->p); - diagbn("gu1p=", gu1p); yu2p = modpow(dss->y, u2, dss->p); - diagbn("yu2p=", yu2p); gu1yu2p = modmul(gu1p, yu2p, dss->p); - diagbn("gu1yu2p=", gu1yu2p); v = modmul(gu1yu2p, One, dss->q); - diagbn("gu1yu2q=v=", v); - diagbn("r=", r); /* * Step 5. v should now be equal to r. @@ -347,28 +353,281 @@ static unsigned char *dss_public_blob(void *key, int *len) static unsigned char *dss_private_blob(void *key, int *len) { - return NULL; /* can't handle DSS private keys */ + struct dss_key *dss = (struct dss_key *) key; + int xlen, bloblen; + int i; + unsigned char *blob, *p; + SHA_State s; + unsigned char digest[20]; + + xlen = (bignum_bitcount(dss->x) + 8) / 8; + + /* + * mpint x, string[20] the SHA of p||q||g. Total 28 + xlen. + * (two length fields and twenty bytes, 20+8=28). + */ + bloblen = 28 + xlen; + blob = smalloc(bloblen); + p = blob; + PUT_32BIT(p, xlen); + p += 4; + for (i = xlen; i--;) + *p++ = bignum_byte(dss->x, i); + PUT_32BIT(p, 20); + SHA_Init(&s); + sha_mpint(&s, dss->p); + sha_mpint(&s, dss->q); + sha_mpint(&s, dss->g); + SHA_Final(&s, digest); + p += 4; + for (i = 0; i < 20; i++) + *p++ = digest[i]; + assert(p == blob + bloblen); + *len = bloblen; + return blob; } static void *dss_createkey(unsigned char *pub_blob, int pub_len, unsigned char *priv_blob, int priv_len) { - return NULL; /* can't handle DSS private keys */ + struct dss_key *dss; + char *pb = (char *) priv_blob; + char *hash; + int hashlen; + SHA_State s; + unsigned char digest[20]; + Bignum ytest; + + dss = dss_newkey((char *) pub_blob, pub_len); + dss->x = getmp(&pb, &priv_len); + getstring(&pb, &priv_len, &hash, &hashlen); + + /* + * Verify details of the key. First check that the hash is + * indeed a hash of p||q||g. + */ + if (hashlen != 20) { + dss_freekey(dss); + return NULL; + } + SHA_Init(&s); + sha_mpint(&s, dss->p); + sha_mpint(&s, dss->q); + sha_mpint(&s, dss->g); + SHA_Final(&s, digest); + if (0 != memcmp(hash, digest, 20)) { + dss_freekey(dss); + return NULL; + } + + /* + * Now ensure g^x mod p really is y. + */ + ytest = modpow(dss->g, dss->x, dss->p); + if (0 != bignum_cmp(ytest, dss->y)) { + dss_freekey(dss); + return NULL; + } + freebn(ytest); + + return dss; } static void *dss_openssh_createkey(unsigned char **blob, int *len) { - return NULL; /* can't handle DSS private keys */ + char **b = (char **) blob; + struct dss_key *dss; + + dss = smalloc(sizeof(struct dss_key)); + if (!dss) + return NULL; + + dss->p = getmp(b, len); + dss->q = getmp(b, len); + dss->g = getmp(b, len); + dss->y = getmp(b, len); + dss->x = getmp(b, len); + + if (!dss->p || !dss->q || !dss->g || !dss->y || !dss->x) { + sfree(dss->p); + sfree(dss->q); + sfree(dss->g); + sfree(dss->y); + sfree(dss->x); + sfree(dss); + return NULL; + } + + return dss; } static int dss_openssh_fmtkey(void *key, unsigned char *blob, int len) { - return -1; /* can't handle DSS private keys */ + struct dss_key *dss = (struct dss_key *) key; + int bloblen, i; + + bloblen = + ssh2_bignum_length(dss->p) + + ssh2_bignum_length(dss->q) + + ssh2_bignum_length(dss->g) + + ssh2_bignum_length(dss->y) + + ssh2_bignum_length(dss->x); + + if (bloblen > len) + return bloblen; + + bloblen = 0; +#define ENC(x) \ + PUT_32BIT(blob+bloblen, ssh2_bignum_length((x))-4); bloblen += 4; \ + for (i = ssh2_bignum_length((x))-4; i-- ;) blob[bloblen++]=bignum_byte((x),i); + ENC(dss->p); + ENC(dss->q); + ENC(dss->g); + ENC(dss->y); + ENC(dss->x); + + return bloblen; } unsigned char *dss_sign(void *key, char *data, int datalen, int *siglen) { - return NULL; /* can't handle DSS private keys */ + /* + * The basic DSS signing algorithm is: + * + * - invent a random k between 1 and q-1 (exclusive). + * - Compute r = (g^k mod p) mod q. + * - Compute s = k^-1 * (hash + x*r) mod q. + * + * This has the dangerous properties that: + * + * - if an attacker in possession of the public key _and_ the + * signature (for example, the host you just authenticated + * to) can guess your k, he can reverse the computation of s + * and work out x = r^-1 * (s*k - hash) mod q. That is, he + * can deduce the private half of your key, and masquerade + * as you for as long as the key is still valid. + * + * - since r is a function purely of k and the public key, if + * the attacker only has a _range of possibilities_ for k + * it's easy for him to work through them all and check each + * one against r; he'll never be unsure of whether he's got + * the right one. + * + * - if you ever sign two different hashes with the same k, it + * will be immediately obvious because the two signatures + * will have the same r, and moreover an attacker in + * possession of both signatures (and the public key of + * course) can compute k = (hash1-hash2) * (s1-s2)^-1 mod q, + * and from there deduce x as before. + * + * - the Bleichenbacher attack on DSA makes use of methods of + * generating k which are significantly non-uniformly + * distributed; in particular, generating a 160-bit random + * number and reducing it mod q is right out. + * + * For this reason we must be pretty careful about how we + * generate our k. Since this code runs on Windows, with no + * particularly good system entropy sources, we can't trust our + * RNG itself to produce properly unpredictable data. Hence, we + * use a totally different scheme instead. + * + * What we do is to take a SHA-512 (_big_) hash of the private + * key x, and then feed this into another SHA-512 hash that + * also includes the message hash being signed. That is: + * + * proto_k = SHA512 ( SHA512(x) || SHA160(message) ) + * + * This number is 512 bits long, so reducing it mod q won't be + * noticeably non-uniform. So + * + * k = proto_k mod q + * + * This has the interesting property that it's _deterministic_: + * signing the same hash twice with the same key yields the + * same signature. + * + * (It doesn't, _per se_, protect against reuse of k. Reuse of + * k is left to chance; all it does is prevent _excessively + * high_ chances of reuse of k due to entropy problems.) + * + * Thanks to Colin Plumb for the general idea of using x to + * ensure k is hard to guess, and to the Cambridge University + * Computer Security Group for helping to argue out all the + * fine details. + */ + struct dss_key *dss = (struct dss_key *) key; + SHA512_State ss; + unsigned char digest[20], digest512[64]; + Bignum proto_k, k, gkp, hash, kinv, hxr, r, s; + unsigned char *bytes; + int nbytes, i; + + SHA_Simple(data, datalen, digest); + + /* + * Hash some identifying text plus x. + */ + SHA512_Init(&ss); + SHA512_Bytes(&ss, "DSA deterministic k generator", 30); + sha512_mpint(&ss, dss->x); + SHA512_Final(&ss, digest512); + + /* + * Now hash that digest plus the message hash. + */ + SHA512_Init(&ss); + SHA512_Bytes(&ss, digest512, sizeof(digest512)); + SHA512_Bytes(&ss, digest, sizeof(digest)); + SHA512_Final(&ss, digest512); + + memset(&ss, 0, sizeof(ss)); + + /* + * Now convert the result into a bignum, and reduce it mod q. + */ + proto_k = bignum_from_bytes(digest512, 64); + k = bigmod(proto_k, dss->q); + freebn(proto_k); + + memset(digest512, 0, sizeof(digest512)); + + /* + * Now we have k, so just go ahead and compute the signature. + */ + gkp = modpow(dss->g, k, dss->p); /* g^k mod p */ + r = bigmod(gkp, dss->q); /* r = (g^k mod p) mod q */ + freebn(gkp); + + hash = bignum_from_bytes(digest, 20); + kinv = modinv(k, dss->q); /* k^-1 mod q */ + hxr = bigmuladd(dss->x, r, hash); /* hash + x*r */ + s = modmul(kinv, hxr, dss->q); /* s = k^-1 * (hash + x*r) mod q */ + freebn(hxr); + freebn(kinv); + freebn(hash); + + /* + * Signature blob is + * + * string "ssh-dss" + * string two 20-byte numbers r and s, end to end + * + * i.e. 4+7 + 4+40 bytes. + */ + nbytes = 4 + 7 + 4 + 40; + bytes = smalloc(nbytes); + PUT_32BIT(bytes, 7); + memcpy(bytes + 4, "ssh-dss", 7); + PUT_32BIT(bytes + 4 + 7, 40); + for (i = 0; i < 20; i++) { + bytes[4 + 7 + 4 + i] = bignum_byte(r, 19 - i); + bytes[4 + 7 + 4 + 20 + i] = bignum_byte(s, 19 - i); + } + freebn(r); + freebn(s); + + *siglen = nbytes; + return bytes; } const struct ssh_signkey ssh_dss = { diff --git a/sshprime.c b/sshprime.c index e6d3b3f9..8bbfb875 100644 --- a/sshprime.c +++ b/sshprime.c @@ -2,6 +2,7 @@ * Prime generation. */ +#include #include "ssh.h" /* @@ -1182,14 +1183,25 @@ static const unsigned short primes[] = { #define NPRIMES (sizeof(primes) / sizeof(*primes)) /* - * Generate a prime. We arrange to select a prime with the property - * (prime % modulus) != residue (to speed up use in RSA). + * Generate a prime. We can deal with various extra properties of + * the prime: + * + * - to speed up use in RSA, we can arrange to select a prime with + * the property (prime % modulus) != residue. + * + * - for use in DSA, we can arrange to select a prime which is one + * more than a multiple of a dirty great bignum. In this case + * `bits' gives the size of the factor by which we _multiply_ + * that bignum, rather than the size of the whole number. */ -Bignum primegen(int bits, int modulus, int residue, +Bignum primegen(int bits, int modulus, int residue, Bignum factor, int phase, progfn_t pfn, void *pfnparam) { int i, k, v, byte, bitsleft, check, checks; - unsigned long delta, moduli[NPRIMES + 1], residues[NPRIMES + 1]; + unsigned long delta; + unsigned long moduli[NPRIMES + 1]; + unsigned long residues[NPRIMES + 1]; + unsigned long multipliers[NPRIMES + 1]; Bignum p, pm1, q, wqp, wqp2; int progress = 0; @@ -1198,15 +1210,18 @@ Bignum primegen(int bits, int modulus, int residue, STARTOVER: - pfn(pfnparam, phase, ++progress); + pfn(pfnparam, PROGFN_PROGRESS, phase, ++progress); /* * Generate a k-bit random number with top and bottom bits set. + * Alternatively, if `factor' is nonzero, generate a k-bit + * random number with the top bit set and the bottom bit clear, + * multiply it by `factor', and add one. */ p = bn_power_2(bits - 1); for (i = 0; i < bits; i++) { if (i == 0 || i == bits - 1) - v = 1; + v = (i != 0 || !factor) ? 1 : 0; else { if (bitsleft <= 0) bitsleft = 8, byte = random_byte(); @@ -1216,14 +1231,26 @@ Bignum primegen(int bits, int modulus, int residue, } bignum_set_bit(p, i, v); } + if (factor) { + Bignum tmp = p; + p = bigmul(tmp, factor); + freebn(tmp); + assert(bignum_bit(p, 0) == 0); + bignum_set_bit(p, 0, 1); + } /* * Ensure this random number is coprime to the first few - * primes, by repeatedly adding 2 to it until it is. + * primes, by repeatedly adding either 2 or 2*factor to it + * until it is. */ for (i = 0; i < NPRIMES; i++) { moduli[i] = primes[i]; residues[i] = bignum_mod_short(p, primes[i]); + if (factor) + multipliers[i] = bignum_mod_short(factor, primes[i]); + else + multipliers[i] = 1; } moduli[NPRIMES] = modulus; residues[NPRIMES] = (bignum_mod_short(p, (unsigned short) modulus) @@ -1231,11 +1258,11 @@ Bignum primegen(int bits, int modulus, int residue, delta = 0; while (1) { for (i = 0; i < (sizeof(moduli) / sizeof(*moduli)); i++) - if (!((residues[i] + delta) % moduli[i])) + if (!((residues[i] + delta * multipliers[i]) % moduli[i])) break; if (i < (sizeof(moduli) / sizeof(*moduli))) { /* we broke */ delta += 2; - if (delta < 2) { + if (delta > 65536) { freebn(p); goto STARTOVER; } @@ -1244,7 +1271,14 @@ Bignum primegen(int bits, int modulus, int residue, break; } q = p; - p = bignum_add_long(q, delta); + if (factor) { + Bignum tmp; + tmp = bignum_from_long(delta); + p = bigmuladd(tmp, factor, q); + freebn(tmp); + } else { + p = bignum_add_long(q, delta); + } freebn(q); /* @@ -1311,7 +1345,7 @@ Bignum primegen(int bits, int modulus, int residue, break; } - pfn(pfnparam, phase, ++progress); + pfn(pfnparam, PROGFN_PROGRESS, phase, ++progress); /* * Compute w^q mod p. diff --git a/sshpubk.c b/sshpubk.c index d5576e8b..2d1f5540 100644 --- a/sshpubk.c +++ b/sshpubk.c @@ -302,64 +302,85 @@ int saversakey(char *filename, struct RSAKey *key, char *passphrase) /* * PuTTY's own format for SSH2 keys is as follows: - * + * * The file is text. Lines are terminated by CRLF, although CR-only * and LF-only are tolerated on input. - * + * * The first line says "PuTTY-User-Key-File-1: " plus the name of the - * algorithm ("ssh-dss", "ssh-rsa" etc. Although, of course, this - * being PuTTY, "ssh-dss" is not supported.) - * + * algorithm ("ssh-dss", "ssh-rsa" etc). + * * The next line says "Encryption: " plus an encryption type. * Currently the only supported encryption types are "aes256-cbc" * and "none". - * + * * The next line says "Comment: " plus the comment string. - * + * * Next there is a line saying "Public-Lines: " plus a number N. * The following N lines contain a base64 encoding of the public * part of the key. This is encoded as the standard SSH2 public key * blob (with no initial length): so for RSA, for example, it will * read - * + * * string "ssh-rsa" * mpint exponent * mpint modulus - * + * * Next, there is a line saying "Private-Lines: " plus a number N, * and then N lines containing the (potentially encrypted) private * part of the key. For the key type "ssh-rsa", this will be * composed of - * + * * mpint private_exponent * mpint p (the larger of the two primes) * mpint q (the smaller prime) * mpint iqmp (the inverse of q modulo p) * data padding (to reach a multiple of the cipher block size) + * + * And for "ssh-dss", it will be composed of + * + * mpint x (the private key parameter) + * string hash (20-byte hash of mpints p || q || g) + * + * Finally, there is a line saying _either_ + * + * - "Private-Hash: " plus a hex representation of a SHA-1 hash of + * the plaintext version of the private part, including the + * final padding. + * + * or + * + * - "Private-MAC: " plus a hex representation of a HMAC-SHA-1 of + * the plaintext version of the private part, including the + * final padding. * - * Finally, there is a line saying "Private-Hash: " plus a hex - * representation of a SHA-1 hash of the plaintext version of the - * private part, including the final padding. + * The key to the MAC is itself a SHA-1 hash of: * + * data "putty-private-key-file-mac-key" + * data passphrase + * + * Encrypted keys should have a MAC, whereas unencrypted ones must + * have a hash. + * * If the key is encrypted, the encryption key is derived from the * passphrase by means of a succession of SHA-1 hashes. Each hash * is the hash of: - * + * * uint32 sequence-number - * string passphrase - * + * data passphrase + * * where the sequence-number increases from zero. As many of these * hashes are used as necessary. - * + * * NOTE! It is important that all _public_ data can be verified * with reference to the _private_ data. There exist attacks based * on modifying the public key but leaving the private section * intact. - * + * * With RSA, this is easy: verify that n = p*q, and also verify - * that e*d == 1 modulo (p-1)(q-1). With DSA (if we were ever to - * support it), we would need to store extra data in the private - * section other than just x. + * that e*d == 1 modulo (p-1)(q-1). With DSA, we need to store + * extra data in the private section other than just x, namely a + * hash of p||q||g. (It's then easy to verify that y is equal to + * g^x mod p.) */ static int read_header(FILE * fp, char *header) @@ -514,16 +535,17 @@ struct ssh2_userkey ssh2_wrong_passphrase = { struct ssh2_userkey *ssh2_load_userkey(char *filename, char *passphrase) { FILE *fp; - char header[40], *b, *comment, *hash; + char header[40], *b, *comment, *mac; const struct ssh_signkey *alg; struct ssh2_userkey *ret; int cipher, cipherblk; unsigned char *public_blob, *private_blob; int public_blob_len, private_blob_len; - int i; + int i, is_mac; + int passlen = passphrase ? strlen(passphrase) : 0; ret = NULL; /* return NULL for most errors */ - comment = hash = NULL; + comment = mac = NULL; public_blob = private_blob = NULL; fp = fopen(filename, "rb"); @@ -536,9 +558,11 @@ struct ssh2_userkey *ssh2_load_userkey(char *filename, char *passphrase) goto error; if ((b = read_body(fp)) == NULL) goto error; - /* Select key algorithm structure. Currently only ssh-rsa. */ + /* Select key algorithm structure. */ if (!strcmp(b, "ssh-rsa")) alg = &ssh_rsa; + else if (!strcmp(b, "ssh-dss")) + alg = &ssh_dss; else { sfree(b); goto error; @@ -588,10 +612,18 @@ struct ssh2_userkey *ssh2_load_userkey(char *filename, char *passphrase) if ((private_blob = read_blob(fp, i, &private_blob_len)) == NULL) goto error; - /* Read the Private-Hash header line. */ - if (!read_header(fp, header) || 0 != strcmp(header, "Private-Hash")) + /* Read the Private-MAC or Private-Hash header line. */ + if (!read_header(fp, header)) goto error; - if ((hash = read_body(fp)) == NULL) + if (0 == strcmp(header, "Private-MAC")) { + if ((mac = read_body(fp)) == NULL) + goto error; + is_mac = 1; + } else if (0 == strcmp(header, "Private-Hash")) { + if ((mac = read_body(fp)) == NULL) + goto error; + is_mac = 0; + } else goto error; fclose(fp); @@ -603,15 +635,12 @@ struct ssh2_userkey *ssh2_load_userkey(char *filename, char *passphrase) if (cipher) { unsigned char key[40]; SHA_State s; - int passlen; if (!passphrase) goto error; if (private_blob_len % cipherblk) goto error; - passlen = strlen(passphrase); - SHA_Init(&s); SHA_Bytes(&s, "\0\0\0\0", 4); SHA_Bytes(&s, passphrase, passlen); @@ -627,21 +656,41 @@ struct ssh2_userkey *ssh2_load_userkey(char *filename, char *passphrase) * Verify the private hash. */ { - char realhash[41]; + char realmac[41]; unsigned char binary[20]; - SHA_Simple(private_blob, private_blob_len, binary); + if (is_mac) { + SHA_State s; + unsigned char mackey[20]; + char header[] = "putty-private-key-file-mac-key"; + + if (!passphrase) /* can't have MAC in unencrypted key */ + goto error; + + SHA_Init(&s); + SHA_Bytes(&s, header, sizeof(header)-1); + SHA_Bytes(&s, passphrase, passlen); + SHA_Final(&s, mackey); + + hmac_sha1_simple(mackey, 20, private_blob, private_blob_len, + binary); + + memset(mackey, 0, sizeof(mackey)); + memset(&s, 0, sizeof(s)); + } else { + SHA_Simple(private_blob, private_blob_len, binary); + } for (i = 0; i < 20; i++) - sprintf(realhash + 2 * i, "%02x", binary[i]); + sprintf(realmac + 2 * i, "%02x", binary[i]); - if (strcmp(hash, realhash)) { - /* An incorrect hash is an unconditional Error if the key is + if (strcmp(mac, realmac)) { + /* An incorrect MAC is an unconditional Error if the key is * unencrypted. Otherwise, it means Wrong Passphrase. */ ret = cipher ? SSH2_WRONG_PASSPHRASE : NULL; goto error; } } - sfree(hash); + sfree(mac); /* * Create and return the key. @@ -668,8 +717,8 @@ struct ssh2_userkey *ssh2_load_userkey(char *filename, char *passphrase) fclose(fp); if (comment) sfree(comment); - if (hash) - sfree(hash); + if (mac) + sfree(mac); if (public_blob) sfree(public_blob); if (private_blob) @@ -702,6 +751,8 @@ char *ssh2_userkey_loadpub(char *filename, char **algorithm, /* Select key algorithm structure. Currently only ssh-rsa. */ if (!strcmp(b, "ssh-rsa")) alg = &ssh_rsa; + else if (!strcmp(b, "ssh-dss")) + alg = &ssh_dss; else { sfree(b); goto error; @@ -863,9 +914,9 @@ int ssh2_save_userkey(char *filename, struct ssh2_userkey *key, int pub_blob_len, priv_blob_len, priv_encrypted_len; int passlen; int cipherblk; - int i; + int i, is_mac; char *cipherstr; - unsigned char priv_hash[20]; + unsigned char priv_mac[20]; /* * Fetch the key component blobs. @@ -895,13 +946,35 @@ int ssh2_save_userkey(char *filename, struct ssh2_userkey *key, memcpy(priv_blob_encrypted, priv_blob, priv_blob_len); /* Create padding based on the SHA hash of the unpadded blob. This prevents * too easy a known-plaintext attack on the last block. */ - SHA_Simple(priv_blob, priv_blob_len, priv_hash); + SHA_Simple(priv_blob, priv_blob_len, priv_mac); assert(priv_encrypted_len - priv_blob_len < 20); - memcpy(priv_blob_encrypted + priv_blob_len, priv_hash, + memcpy(priv_blob_encrypted + priv_blob_len, priv_mac, priv_encrypted_len - priv_blob_len); - /* Now create the _real_ private hash. */ - SHA_Simple(priv_blob_encrypted, priv_encrypted_len, priv_hash); + /* Now create the private MAC. */ + if (passphrase) { + SHA_State s; + unsigned char mackey[20]; + char header[] = "putty-private-key-file-mac-key"; + + passlen = strlen(passphrase); + + SHA_Init(&s); + SHA_Bytes(&s, header, sizeof(header)-1); + SHA_Bytes(&s, passphrase, passlen); + SHA_Final(&s, mackey); + + hmac_sha1_simple(mackey, 20, + priv_blob_encrypted, priv_encrypted_len, + priv_mac); + is_mac = 1; + + memset(mackey, 0, sizeof(mackey)); + memset(&s, 0, sizeof(s)); + } else { + SHA_Simple(priv_blob_encrypted, priv_encrypted_len, priv_mac); + is_mac = 0; + } if (passphrase) { char key[40]; @@ -919,6 +992,9 @@ int ssh2_save_userkey(char *filename, struct ssh2_userkey *key, SHA_Final(&s, key + 20); aes256_encrypt_pubkey(key, priv_blob_encrypted, priv_encrypted_len); + + memset(key, 0, sizeof(key)); + memset(&s, 0, sizeof(s)); } fp = fopen(filename, "w"); @@ -931,9 +1007,12 @@ int ssh2_save_userkey(char *filename, struct ssh2_userkey *key, base64_encode(fp, pub_blob, pub_blob_len); fprintf(fp, "Private-Lines: %d\n", base64_lines(priv_encrypted_len)); base64_encode(fp, priv_blob_encrypted, priv_encrypted_len); - fprintf(fp, "Private-Hash: "); + if (is_mac) + fprintf(fp, "Private-MAC: "); + else + fprintf(fp, "Private-Hash: "); for (i = 0; i < 20; i++) - fprintf(fp, "%02x", priv_hash[i]); + fprintf(fp, "%02x", priv_mac[i]); fprintf(fp, "\n"); fclose(fp); return 1; diff --git a/sshrsag.c b/sshrsag.c index 9e543c9a..eb714ad6 100644 --- a/sshrsag.c +++ b/sshrsag.c @@ -6,28 +6,6 @@ #define RSA_EXPONENT 37 /* we like this prime */ -#if 0 /* bignum diagnostic function */ -static void diagbn(char *prefix, Bignum md) -{ - int i, nibbles, morenibbles; - static const char hex[] = "0123456789ABCDEF"; - - printf("%s0x", prefix ? prefix : ""); - - nibbles = (3 + bignum_bitcount(md)) / 4; - if (nibbles < 1) - nibbles = 1; - morenibbles = 4 * md[0] - nibbles; - for (i = 0; i < morenibbles; i++) - putchar('-'); - for (i = nibbles; i--;) - putchar(hex[(bignum_byte(md, i / 2) >> (4 * (i % 2))) & 0xF]); - - if (prefix) - putchar('\n'); -} -#endif - int rsa_generate(struct RSAKey *key, int bits, progfn_t pfn, void *pfnparam) { @@ -61,14 +39,18 @@ int rsa_generate(struct RSAKey *key, int bits, progfn_t pfn, * time. We do this in 16-bit fixed point, so 29.34 becomes * 0x1D.57C4. */ - pfn(pfnparam, -1, -0x1D57C4 / (bits / 2)); - pfn(pfnparam, -2, -0x1D57C4 / (bits - bits / 2)); - pfn(pfnparam, -3, 5); + pfn(pfnparam, PROGFN_PHASE_EXTENT, 1, 0x10000); + pfn(pfnparam, PROGFN_EXP_PHASE, 1, -0x1D57C4 / (bits / 2)); + pfn(pfnparam, PROGFN_PHASE_EXTENT, 2, 0x10000); + pfn(pfnparam, PROGFN_EXP_PHASE, 2, -0x1D57C4 / (bits - bits / 2)); + pfn(pfnparam, PROGFN_PHASE_EXTENT, 3, 0x4000); + pfn(pfnparam, PROGFN_LIN_PHASE, 3, 5); + pfn(pfnparam, PROGFN_READY, 0, 0); /* * We don't generate e; we just use a standard one always. */ - key->exponent = bignum_from_short(RSA_EXPONENT); + key->exponent = bignum_from_long(RSA_EXPONENT); /* * Generate p and q: primes with combined length `bits', not @@ -77,8 +59,10 @@ int rsa_generate(struct RSAKey *key, int bits, progfn_t pfn, * general that's slightly more fiddly to arrange. By choosing * a prime e, we can simplify the criterion.) */ - key->p = primegen(bits / 2, RSA_EXPONENT, 1, 1, pfn, pfnparam); - key->q = primegen(bits - bits / 2, RSA_EXPONENT, 1, 2, pfn, pfnparam); + key->p = primegen(bits / 2, RSA_EXPONENT, 1, NULL, + 1, pfn, pfnparam); + key->q = primegen(bits - bits / 2, RSA_EXPONENT, 1, NULL, + 2, pfn, pfnparam); /* * Ensure p > q, by swapping them if not. @@ -94,21 +78,21 @@ int rsa_generate(struct RSAKey *key, int bits, progfn_t pfn, * the other helpful quantities: n=pq, d=e^-1 mod (p-1)(q-1), * and (q^-1 mod p). */ - pfn(pfnparam, 3, 1); + pfn(pfnparam, PROGFN_PROGRESS, 3, 1); key->modulus = bigmul(key->p, key->q); - pfn(pfnparam, 3, 2); + pfn(pfnparam, PROGFN_PROGRESS, 3, 2); pm1 = copybn(key->p); decbn(pm1); qm1 = copybn(key->q); decbn(qm1); phi_n = bigmul(pm1, qm1); - pfn(pfnparam, 3, 3); + pfn(pfnparam, PROGFN_PROGRESS, 3, 3); freebn(pm1); freebn(qm1); key->private_exponent = modinv(key->exponent, phi_n); - pfn(pfnparam, 3, 4); + pfn(pfnparam, PROGFN_PROGRESS, 3, 4); key->iqmp = modinv(key->q, key->p); - pfn(pfnparam, 3, 5); + pfn(pfnparam, PROGFN_PROGRESS, 3, 5); /* * Clean up temporary numbers. diff --git a/sshsha.c b/sshsha.c index 6031685a..5b50d7ec 100644 --- a/sshsha.c +++ b/sshsha.c @@ -271,6 +271,19 @@ static int sha1_verify(unsigned char *blk, int len, unsigned long seq) return !memcmp(correct, blk + len, 20); } +void hmac_sha1_simple(void *key, int keylen, void *data, int datalen, + unsigned char *output) { + SHA_State s1, s2; + unsigned char intermediate[20]; + + sha1_key(&s1, &s2, key, keylen); + SHA_Bytes(&s1, data, datalen); + SHA_Final(&s1, intermediate); + + SHA_Bytes(&s2, intermediate, 20); + SHA_Final(&s2, output); +} + const struct ssh_mac ssh_sha1 = { sha1_cskey, sha1_sckey, sha1_generate,