From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Sat Mar 1 00:08:13 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E6BA11A0067 for ; Sat, 1 Mar 2014 00:08:12 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id PDIgGiU-va8m for ; Sat, 1 Mar 2014 00:08:11 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 8165D1A076F for ; Sat, 1 Mar 2014 00:08:11 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id 4A20114A504; Sat, 1 Mar 2014 08:08:07 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: by mail.netbsd.org (Postfix, from userid 1347) id E0B4514A502; Sat, 1 Mar 2014 08:08:06 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 1C49414A518 for ; Fri, 28 Feb 2014 13:51:33 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id 7gFgv0e4dzCs for ; Fri, 28 Feb 2014 13:51:32 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id EA85114A4F2 for ; Fri, 28 Feb 2014 13:51:28 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1393595492; x=1425131492; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=gtbkfjieSKPUApHa4iWaH/ljzIgYhnNa3f3X+jFbZYE=; b=K70ewi66jKR5bgGLL5J7wnZzNWd7T21Rj5ZquBT9xM4EyM6qTOrHfwnX z8ZNv2hZB0n9IT2PGd/O4/iCSjj3z35P8TZTAbVgTqcyYZIf0AvJ4gMi3 2k+WPw9+pTP1B0lLlWl3ypz7h3TIcV2NuLVltW72fBzkSF+aipdx0GpMq 4=; X-IronPort-AV: E=Sophos;i="4.97,561,1389697200"; d="scan'208";a="236508111" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.112 - Outgoing - Outgoing Received: from uxchange10-fe1.uoa.auckland.ac.nz ([130.216.4.112]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 01 Mar 2014 01:20:48 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe1.UoA.auckland.ac.nz ([130.216.4.112]) with mapi id 14.03.0174.001; Sat, 1 Mar 2014 01:20:47 +1300 From: Peter Gutmann To: "" , "ietf-ssh@NetBSD.org" Subject: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Topic: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Index: Ac80f4KYhJZr8H2uQwmODWcaii6Djw== Date: Fri, 28 Feb 2014 12:20:47 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C73723848D4@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list I can has SHA-1 hashes for RFC 2409/3526 MODP groups?=0A= =0A= The MODP groups for DH specified in RFC 2409 and 3526 seem to be widely use= d=0A= in things like SSH and SSL/TLS, however unlike the RFC 5114 groups there's = no=0A= subgroup given and so no way to verify that the prime hasn't been corrupted= in=0A= some way (the generator is easy, it's always 2). OTOH the RFC 5114 groups= =0A= have stupid generators so I don't know why anyone would use them.=0A= =0A= In any case I'd like to have a means of verifying the validity of the data = for=0A= the RFC 2409/3526 primes as stored in memory, but if I generate my own SHA-= 1=0A= hashes then there's the risk that I'm verifying flawed data. Does anyone h= ave=0A= SHA-1 hash values for the RFC 2409/3526 primes, i.e. the 1024/1536/2048/etc= -=0A= bit values in the two RFCs? The values I've got are:=0A= =0A= RFC 2409, 1024-bit prime: c0 33 bd 43 51 fb a3 73 25 45 ea 2e 01 6d 52 b0 .= ..=0A= RFC 3526, 1536-bit prime: 49 ec ab a9 72 7a 1a f0 63 60 82 c4 67 48 5a 1a .= ..=0A= RFC 3526, 2048-bit prime: b9 5c 79 9a a5 dd 38 8c 6d f5 e7 23 98 cb 9d 7d .= ..=0A= RFC 3526, 3072-bit prime: 94 1a 04 77 38 fe 55 33 33 69 e2 b3 86 b6 d6 18 .= ..=0A= =0A= Peter.= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Sat Mar 1 11:04:18 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7791F1A0A2E for ; Sat, 1 Mar 2014 11:04:18 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.553 X-Spam-Level: X-Spam-Status: No, score=0.553 tagged_above=-999 required=5 tests=[BAYES_50=0.8, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id d6qkCGbOQDVb for ; Sat, 1 Mar 2014 11:04:16 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 782CE1A0A2A for ; Sat, 1 Mar 2014 11:04:16 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id 4692114A5CE; Sat, 1 Mar 2014 19:04:13 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: by mail.netbsd.org (Postfix, from userid 1347) id E46FB14A5CC; Sat, 1 Mar 2014 19:04:12 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 0542514A102 for ; Sat, 1 Mar 2014 16:02:37 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id lR42LnQ44-Hw for ; Sat, 1 Mar 2014 16:02:36 +0000 (UTC) Received: from vsp6.ballou.se (vsp6.ballou.se [91.189.40.85]) by mail.netbsd.org (Postfix) with SMTP id A728714A0A9 for ; Sat, 1 Mar 2014 16:02:34 +0000 (UTC) Received: from nmail1.ballou.se (unknown [10.0.0.116]) by vsp6.ballou.se (Halon Mail Gateway) with ESMTP; Sat, 1 Mar 2014 16:02:07 +0100 (CET) Received: from [192.168.0.195] (c-a2c1e555.06-134-73746f39.cust.bredbandsbolaget.se [85.229.193.162]) (Authenticated sender: henrick@streamsec.se) by nmail1.ballou.se (Postfix) with ESMTPSA id 8AF8F1E09F; Sat, 1 Mar 2014 16:02:13 +0100 (CET) Message-ID: <5311F652.4090804@streamsec.se> Date: Sat, 01 Mar 2014 16:01:38 +0100 From: =?UTF-8?B?SGVucmljayBIZWxsc3Ryw7Zt?= Reply-To: henrick@streamsec.se User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0 MIME-Version: 1.0 To: Geoffrey Keating , Peter Gutmann CC: "" , "ietf-ssh@NetBSD.org" Subject: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? References: <9A043F3CF02CD34C8E74AC1594475C73723848D4@uxcn10-6.UoA.auckland.ac.nz> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 8bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On 2014-02-28 22:22, Geoffrey Keating wrote: > I'd encourage you to do the derivation again: compute > > 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 } > > and verify that it's prime. I don't think any special security > measures were taken during the creation of RFC 3526, you'd think by > now someone would have noticed if the 'primes' weren't prime or didn't > match the claimed polynomial, but if everyone thinks someone else has > checked... There is more. 1. The MODP primes are supposed to be safe primes (i.e. primes on the form p = 2q+1 where q is also prime). Furthermore, 2 will be a generator of the large sub group of order q, rather than of the entire multiplicative group of order 2q. 2. Pi might be calculated using the Bailey–Borwein–Plouffe formula. I calculated it for the first 2048 hexadecimal digits, which was a sufficiently good approximation for all of the MODP groups up to the 8192 bit one. 3. All of the MODP primes are on the form p = 2^n - 2^(n-64) + 2^64( [2^(n-130)pi] + k). The value k is supposed to be the least positive integer, such that p is a safe prime. This check is important, to rule out that any candidates have been deliberately skipped, because they lack some (hidden) property. I have generated the primes 1024, 2048, 3072, 4096, 6144 and 8192 from the formulae and verified that: a: The numbers match the numbers in the RFCs. b: The numbers are safe primes (using both Miller-Rabin tests and Lucas tests on q = (p-1)/2, and then the Pocklington Criterion on p). c: The small constant k is indeed the least positive integer such that the number is a safe prime. (Well, to be honest I am still running this test for the largest group, just make sure once more.) From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Sun Mar 2 07:48:12 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 164FB1A07FF for ; Sun, 2 Mar 2014 07:48:12 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 2.225 X-Spam-Level: ** X-Spam-Status: No, score=2.225 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, DKIM_ADSP_CUSTOM_MED=0.001, FREEMAIL_FROM=0.001, IXHASH_X2=2.5, RCVD_IN_SORBS_WEB=0.77, RP_MATCHES_RCVD=-0.547] autolearn=no Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lFgeWd2Xl0bi for ; Sun, 2 Mar 2014 07:48:11 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 78FB01A0801 for ; Sun, 2 Mar 2014 07:48:11 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id 9EA9314A676; Sun, 2 Mar 2014 15:48:06 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 04A2314A673 for ; Sun, 2 Mar 2014 15:48:06 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id G1iPgNu22D7n for ; Sun, 2 Mar 2014 15:48:05 +0000 (UTC) Received: from exchange.neagenia.gr (exchange.neagenia.gr [195.251.16.156]) by mail.netbsd.org (Postfix) with SMTP id 3EF2E14A646 for ; Sun, 2 Mar 2014 15:48:03 +0000 (UTC) Received: from exchange.neagenia.gr ([188.162.15.110] RDNS failed) by exchange.neagenia.gr with Microsoft SMTPSVC(6.0.3790.4675); Sun, 2 Mar 2014 16:44:48 +0200 From: tarrageros@gmail.com To: lcollins@wncn.com Subject: Klientskie bazi Email: tarrageros@gmail.com Message-ID: X-OriginalArrivalTime: 02 Mar 2014 14:44:49.0303 (UTC) FILETIME=[F66C8270:01CF3625] Date: 2 Mar 2014 16:44:49 +0200 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Klientskie bazi Email: tarrageros@gmail.com From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Fri Mar 7 13:40:10 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BD2291A0111 for ; Fri, 7 Mar 2014 13:40:10 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 0B2hKMv0xuIy for ; Fri, 7 Mar 2014 13:40:07 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 9F4A61A01EE for ; Fri, 7 Mar 2014 13:40:07 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id C96CF14A33D; Fri, 7 Mar 2014 21:40:00 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: by mail.netbsd.org (Postfix, from userid 1347) id 661AC14A331; Fri, 7 Mar 2014 21:40:00 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 0FA1814A31C for ; Fri, 7 Mar 2014 12:09:23 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id 5q1VeERiQv3D for ; Fri, 7 Mar 2014 12:09:22 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 2ED9C14A30B for ; Fri, 7 Mar 2014 12:09:18 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1394194161; x=1425730161; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=wfXAd2o10TrUMEjt5mPKZnyuB+nkKbXf45pBjKKqO1E=; b=IplY5mw2ZkQ1SSP0jwNnbfbIm++ubmiphWOTXrq9IbslYiincAk+YyIM pSqVh/Z/zuNk/qky6LcQrMHdqbCyQBnIztayjUaNVex0BU4UiqbxwoKuN is6/VcTSHNKXxz707b4c6iwwo4F0lg/stKZyW3L6MI/NemyoRTO75oT2a I=; X-IronPort-AV: E=Sophos;i="4.97,607,1389697200"; d="scan'208";a="238090304" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.125 - Outgoing - Outgoing Received: from uxchange10-fe3.uoa.auckland.ac.nz ([130.216.4.125]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 08 Mar 2014 01:09:15 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe3.UoA.auckland.ac.nz ([130.216.4.125]) with mapi id 14.03.0174.001; Sat, 8 Mar 2014 01:09:14 +1300 From: Peter Gutmann To: "" , "ietf-ssh@netbsd.org" Subject: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Topic: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Index: Ac85/g6s1yWJL+P+QD2gH1b9ES47kw== Date: Fri, 7 Mar 2014 12:09:14 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Geoffrey Keating writes:=0A= =0A= >I'd encourage you to do the derivation again: compute=0A= >=0A= >2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 }=0A= >=0A= >and verify that it's prime.=0A= =0A= That assumes that (a) my calculation of that (what on earth is "{ [2^1918 p= i]=0A= + 124476 }", for example?) will be correct, and (b) my overall calculations= =0A= will also be correct, which is more or less the thing I'm trying to avoid: = I'd=0A= like an independent check on the values so that if I've messed up anywhere,= I=0A= can detect it. Getting a hash of the byte string seems to be the easiest w= ay=0A= to do this.=0A= =0A= Speaking of doing the derivation again, do we know if anyone's actually tri= ed=0A= to reproduce the values given in the RFC? I'm assuming it came from someth= ing=0A= like Mathematica which I don't have directly available, and Mathics gives m= e,=0A= for '2^2048 - 2^1984 - 1 + 2^64 * ((2^1918 * pi) + 124476)' the not terribl= y=0A= helpful:=0A= =0A= 323170060713110072989629682791328204232235930243637964344400413166715435658= 73=0A= 440916351244591771371847086149164662580591029693953927426555290878070964232= 927=0A= 695481445976665844136502242593753417365574610202650424305468123288740527986= 069=0A= 345182600707793335155055488870009358517077286832777252562865057729531709228= 943=0A= 077561263607903104272439999956067085492978564938102680241320640398099496994= 465=0A= 906209396510474094085543397979368739086794572799533369234200999216018730602= 022=0A= 705374745273152831923492968543993770580612325275982255795197317429444934474= 851=0A= 545487458964741061916562950289834595688065052813922041488166690320547839+18= 446=0A= 744073709551616(124476+2374278629519728535136746592397124249767311765867127= 918=0A= 570023908264629157167400846877644685208027625404323721209699497484526969413= 701=0A= 467981853825962047983251924686564710804944458674372390943883621415233322481= 794=0A= 551936525204552984042331894647861447774178735086820277226677386425466403176= 594=0A= 780063984777699548807262435341787904726367875755303786443248143665183526702= 686=0A= 263900917281336138003954386069156827670111514514969010644898285176470534075= 324=0A= 491432175331619907825556678522705737282121499935633499250184851491021463412= 446=0A= 9728944541006176128457062647724487151147320327110918144pi)=0A= =0A= which if fed to bc as:=0A= =0A= 323170060713110072989629682791328204232235930243637964344400413166715435658= 73=0A= 440916351244591771371847086149164662580591029693953927426555290878070964232= 927=0A= 695481445976665844136502242593753417365574610202650424305468123288740527986= 069=0A= 345182600707793335155055488870009358517077286832777252562865057729531709228= 943=0A= 077561263607903104272439999956067085492978564938102680241320640398099496994= 465=0A= 906209396510474094085543397979368739086794572799533369234200999216018730602= 022=0A= 705374745273152831923492968543993770580612325275982255795197317429444934474= 851=0A= 545487458964741061916562950289834595688065052813922041488166690320547839+18= 446=0A= 744073709551616*(124476+237427862951972853513674659239712424976731176586712= 791=0A= 857002390826462915716740084687764468520802762540432372120969949748452696941= 370=0A= 146798185382596204798325192468656471080494445867437239094388362141523332248= 179=0A= 455193652520455298404233189464786144777417873508682027722667738642546640317= 659=0A= 478006398477769954880726243534178790472636787575530378644324814366518352670= 268=0A= 626390091728133613800395438606915682767011151451496901064489828517647053407= 532=0A= 449143217533161990782555667852270573728212149993563349925018485149102146341= 244=0A= 69728944541006176128457062647724487151147320327110918144*pi)=0A= =0A= is reported to be:=0A= =0A= 323170060713110072989629682791328204232235930243637964344400413166715435658= 734=0A= 409163512445917713718470861491646625805910296939539274265552908780709642329= 276=0A= 954814459766658441365022425937534173655746102026504243054681232887405279860= 693=0A= 451826007077933351550554888700093585170772868327772525628650577295317092289= 430=0A= 775612636079031042724399999560670854929785649381026802413206403980994969944= 659=0A= 062093965104740940855433979793687390867945727995333692342009992160187306020= 227=0A= 053747452731528319234929685439937705806123252759822557951973174294449344748= 515=0A= 45487458964741061916562950289834595688065052816218218403485760467501055=0A= =0A= which is:=0A= =0A= 0xffffffffffffffff000000000000000000000000000000000000000000000000000000000= 000=0A= 000000000000000000000000000000000000000000000000000000000000000000000000000= 000=0A= 000000000000000000000000000000000000000000000000000000000000000000000000000= 000=0A= 000000000000000000000000000000000000000000000000000000000000000000000000000= 000=0A= 000000000000000000000000000000000000000000000000000000000000000000000000000= 000=0A= 000000000000000000000000000000000000000000000000000000000000000000000000000= 000=0A= 00000000000000000000000001e63bffffffffffffffff=0A= =0A= which isn't right.=0A= =0A= Peter.= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Fri Mar 7 13:40:26 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id DF58F1A013A for ; Fri, 7 Mar 2014 13:40:26 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id abZOjFUkYdNB for ; Fri, 7 Mar 2014 13:40:25 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id C47621A0111 for ; Fri, 7 Mar 2014 13:40:25 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id 6376614A350; Fri, 7 Mar 2014 21:40:16 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: by mail.netbsd.org (Postfix, from userid 1347) id 06F2C14A331; Fri, 7 Mar 2014 21:40:16 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id E2A4E14A34A for ; Fri, 7 Mar 2014 12:13:05 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id 0Ev5Q_43KChr for ; Fri, 7 Mar 2014 12:13:05 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id E425C14A343 for ; Fri, 7 Mar 2014 12:13:04 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1394194385; x=1425730385; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=C0ISA83fEuplQkCDyzxZwERgrulljvtCHfhVmHgZEdo=; b=l8JDogjabyg7xXDCCgXRaiSNUX/QhYfNvP2G62sjpPAPN7ciQ94LXo5S 4fn1kfOxXBesBdHV1BH5K7TgMDerbot+E+f5pzlxx5mgkSyert0qSuV9e fQy3XiPqugXIP7Q6XZ3Fyspqh8wbrkZtOq1tGsYQNWzXeFpjJ04F7l9UY w=; X-IronPort-AV: E=Sophos;i="4.97,607,1389697200"; d="scan'208";a="238090496" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.106 - Outgoing - Outgoing Received: from uxchange10-fe2.uoa.auckland.ac.nz ([130.216.4.106]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 08 Mar 2014 01:13:03 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe2.UoA.auckland.ac.nz ([130.216.4.106]) with mapi id 14.03.0174.001; Sat, 8 Mar 2014 01:13:03 +1300 From: Peter Gutmann To: "" , "ietf-ssh@netbsd.org" Subject: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Topic: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Index: Ac85/pZtcjNXgQKnRyqzj14Zyiee9A== Date: Fri, 7 Mar 2014 12:13:02 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C7372387CAB@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list =3D?UTF-8?B?SGVucmljayBIZWxsc3Ryw7Zt?=3D writes:=0A= =0A= >I have generated the primes 1024, 2048, 3072, 4096, 6144 and 8192 from the= =0A= >formulae and verified that:=0A= >=0A= >a: The numbers match the numbers in the RFCs.=0A= >b: The numbers are safe primes (using both Miller-Rabin tests and Lucas te= sts=0A= >on q =3D (p-1)/2, and then the Pocklington Criterion on p).=0A= >c: The small constant k is indeed the least positive integer such that the= =0A= >number is a safe prime. (Well, to be honest I am still running this test f= or=0A= >the largest group, just make sure once more.)=0A= =0A= Ah, OK, thanks. So we've got independent verification :-).=0A= =0A= Peter.= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Fri Mar 7 15:18:28 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 5AFB91A0316 for ; Fri, 7 Mar 2014 15:18:28 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -1.047 X-Spam-Level: X-Spam-Status: No, score=-1.047 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 6cy2D-WKQ6-b for ; Fri, 7 Mar 2014 15:18:26 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 9BB671A031A for ; Fri, 7 Mar 2014 15:18:26 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id DF79714A26F; Fri, 7 Mar 2014 23:18:19 +0000 (UTC) Delivered-To: ietf-ssh@NetBSD.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 3AEEF14A26D for ; Fri, 7 Mar 2014 23:18:13 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id H2brooI3GgAs for ; Fri, 7 Mar 2014 23:18:12 +0000 (UTC) Received: from Chip.Rodents-Montreal.ORG (Chip.Rodents-Montreal.ORG [216.46.0.66]) by mail.netbsd.org (Postfix) with ESMTP id DA7B114A25E for ; Fri, 7 Mar 2014 23:18:11 +0000 (UTC) Received: (from mouse@localhost) by Chip.Rodents-Montreal.ORG (8.8.8/8.8.8) id SAA28740; Fri, 7 Mar 2014 18:18:11 -0500 (EST) Date: Fri, 7 Mar 2014 18:18:11 -0500 (EST) From: Mouse Message-Id: <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> Mime-Version: 1.0 Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 8bit X-Erik-Conspiracy: There is no Conspiracy - and if there were I wouldn't be part of it anyway. X-Message-Flag: Microsoft: the company who gave us the botnet zombies. X-Composition-Start-Date: Fri, 7 Mar 2014 17:20:47 -0500 (EST) To: tls@ietf.org, ietf-ssh@NetBSD.org Subject: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? In-Reply-To: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list >> I'd encourage you to do the derivation again: compute >> 2^2048 - 2^1984 - 1 + 2^64 * { [2^1918 pi] + 124476 } >> and verify that it's prime. Or, at least, that it's probably prime. > That assumes that (a) my calculation of that (what on earth is "{ > [2^1918 pi] + 124476 }", for example?) Take pi, multiply by the 1918th power of two, discard the fractional part, and add 124476. Or, at least, that's what I'd read it as. This means computing pi to nearly two thousand bits of precision (or finding a reference value you trust enough), but that's really the only hard part. > will be correct, and (b) my overall calculations will also be > correct, which is more or less the thing I'm trying to avoid: I'd > like an independent check on the values so that if I've messed up > anywhere, I can detect it. Well, if you get the same thing the RFC specifies, that's reasonable confirmation you've done the calculation correctly. > Getting a hash of the byte string seems to be the easiest way to do > this. Not just computing it and comparing it against the value in RFC3526? > Speaking of doing the derivation again, do we know if anyone's > actually tried to reproduce the values given in the RFC? I'm > assuming it came from something like Mathematica which I don't have > directly available, and Mathics gives me, for '2^2048 - 2^1984 - 1 + > 2^64 * ((2^1918 * pi) + 124476)' the not terribly helpful: Few general-purpose calculator programs will actually compute pi to the necessary number of places. I know of someone who tried such a thing and got a wrong result which turned out to match the value resulting from using the irrational number in question (pi, sqrt(2), whatever it was) truncated to IEEE double precision. > [...] > which if fed to bc as: > [...]+[...]*(124476+[...]*pi) > is reported to be: > [...] > which is: > 0xffffffffffffffff000000000000000000000000000000000000000 > 000 > 000000000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000000000 > 000000000000000000000000000000000000000000000000000000000000000000000000000000 > 00000000000000000000000001e63bffffffffffffffff > which isn't right. However, if you add 18 more 0s to the long string of them (which the formatting makes it look likely got dropped in whatever produced the weird line breaks above - if I add 18 more 0s and paste the first two lines together, the result is exactly as long as the next five lines), that _is_ 2^2048 - 2^1984 - 1 + (2^64 * 124476). That is, it's what you get if you take pi to be 0. I suspect your bc didn't recognize the character string "pi" and treated it as an unset variable or some such, effectively replacing it with 0. I have a calculator program capable of working with numbers of this size. I told it to compute pi in hex to 500 places; truncating the result to 1918 fraction bits gives (still in hex, linebreaks added for email consumption) 3.243f6a8885a308d313198a2e03707344a4093822299f31d0082efa98ec4e6c 89452821e638d01377be5466cf34e90c6cc0ac29b7c97c50dd3f84d5b5b54709 179216d5d98979fb1bd1310ba698dfb5ac2ffd72dbd01adfb7b8e1afed6a267e 96ba7c9045f12c7f9924a19947b3916cf70801f2e2858efc16636920d871574e 69a458fea3f4933d7e0d95748f728eb658718bcd5882154aee7b54a41dc25a59 b59c30d5392af26013c5d1b023286085f0ca417918b8db38ef8e79dcb0603a18 0e6c9e0e8bb01e8a3ed71577c1bd314b2778af2fda55605c60e65525f3aa55ab 945748986263e8144055ca396a2aab10b4 Setting pi to this value and telling it to compute (still working in hex, hence the #d prefixes all over and the cvt() call because it doesn't like mixed-base arithmetic) pow(2,#d2048)-pow(2,#d1984)-1+(pow(2,#d64)*((pi*pow(2,#d1918))+cvt(#d124476,#d16))) I get (again, line breaks added for email) ffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74 020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f1437 4fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7ed ee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf05 98da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb 9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3b e39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf695581718 3995497cea956ae515d2261898fa051015728e5a8aacaa68ffffffffffffffff which is the value in RFC3526 (after case conversion and whitespace fixup, the two text strings are identical). I haven't done anything about checking it for primality. If anyone would like to look at the calculator program in question, git clone git://git.rodents-montreal.org/Mouse/calc and look at calc.c. It might even build for you, though not with the Makefile from the git repo unless you pick up ftp.rodents-montreal.org:/mouse/local/src/makefiles/makefiles-20100906/local-prog and maybe not even then. (icalc.c is ignorable - known broken.) /~\ The ASCII Mouse \ / Ribbon Campaign X Against HTML mouse@rodents-montreal.org / \ Email! 7D C8 61 52 5D E7 2D 39 4E F1 31 3E E8 B3 27 4B From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Fri Mar 7 17:21:39 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 331031A032A for ; Fri, 7 Mar 2014 17:21:39 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8JRvQMTY42db for ; Fri, 7 Mar 2014 17:21:37 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 9B6EF1A02FB for ; Fri, 7 Mar 2014 17:21:37 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id D361F14A2F7; Sat, 8 Mar 2014 01:21:30 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 9B50214A2EB for ; Sat, 8 Mar 2014 01:21:28 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id xqElf-NCDk0c for ; Sat, 8 Mar 2014 01:21:28 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 7E7E314A2E4 for ; Sat, 8 Mar 2014 01:21:23 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1394241688; x=1425777688; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=a6ZyYuNSrJPvS2spYarfHnqY6GRfTTpjsMyk90tj8Rw=; b=TfZtrNzTNTqAbFmzRXxGkwGnyz5vSiy9ysOpJqgs/vKOptgYjylf9gRb MMx3whPsUSw2nxYwZEahOb4CK/l2yNwXPfPdq77ptCQIXnvw3efu9pcdF COeb3a1lDHS8bjvL7gBxAE+RJcCPxGWJkAyQQHXrMOLco1E1BAw2vityQ Y=; X-IronPort-AV: E=Sophos;i="4.97,611,1389697200"; d="scan'208";a="238152508" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.171 - Outgoing - Outgoing Received: from uxchange10-fe4.uoa.auckland.ac.nz ([130.216.4.171]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 08 Mar 2014 14:21:22 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe4.UoA.auckland.ac.nz ([130.216.4.171]) with mapi id 14.03.0174.001; Sat, 8 Mar 2014 14:21:21 +1300 From: Peter Gutmann To: "tls@ietf.org" , "ietf-ssh@NetBSD.org" Subject: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Topic: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Thread-Index: Ac86bLZXNVJsR7G6T9eCT9gPxa4M7A== Date: Sat, 8 Mar 2014 01:21:20 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C7372388364@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Mouse writes:=0A= =0A= >> Getting a hash of the byte string seems to be the easiest way to do=0A= >> this.=0A= >=0A= >Not just computing it and comparing it against the value in RFC3526?=0A= =0A= It depends what you're trying to verify. If the question is "are the value= s=0A= given in RFC 2409/3526 correct?" then that's the way to do it (and thanks f= or=0A= pointing out the issue with bc and pi :-). If the question is "does the by= te=0A= string I currently have in memory correspond to the data in the RFC" then= =0A= shelling out to Mathematica and bc isn't really an option, a SHA-1 hash for= =0A= quick verification seems the best way to go.=0A= =0A= Peter.=0A= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Sat Mar 8 03:30:05 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 59CFA1A024B for ; Sat, 8 Mar 2014 03:30:05 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.6 X-Spam-Level: X-Spam-Status: No, score=0.6 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, MIME_8BIT_HEADER=0.3, RCVD_IN_BL_SPAMCOP_NET=1.347, RP_MATCHES_RCVD=-0.547] autolearn=no Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id rlzsETLwyoNq for ; Sat, 8 Mar 2014 03:30:04 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 050C11A0114 for ; Sat, 8 Mar 2014 03:30:04 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id 1CAA614A2DD; Sat, 8 Mar 2014 11:29:57 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 01D3D14A2BD for ; Sat, 8 Mar 2014 11:29:55 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id FcnObtRjcB3u for ; Sat, 8 Mar 2014 11:29:54 +0000 (UTC) Received: from vsp1.ballou.se (vsp1.ballou.se [91.189.40.82]) by mail.netbsd.org (Postfix) with SMTP id DE80F14A2B9 for ; Sat, 8 Mar 2014 11:29:53 +0000 (UTC) Received: from nmail1.ballou.se (unknown [10.0.0.116]) by vsp1.ballou.se (Halon Mail Gateway) with ESMTP; Sat, 8 Mar 2014 11:27:32 +0100 (CET) Received: from [192.168.0.10] (s83-191-225-212.cust.tele2.se [83.191.225.212]) (Authenticated sender: henrick@streamsec.se) by nmail1.ballou.se (Postfix) with ESMTPSA id C20FB1E0A6; Sat, 8 Mar 2014 11:29:34 +0100 (CET) Message-ID: <531AF11B.3050106@streamsec.se> Date: Sat, 08 Mar 2014 11:29:47 +0100 From: =?ISO-8859-1?Q?Henrick_Hellstr=F6m?= User-Agent: Mozilla/5.0 (Windows NT 6.1; rv:24.0) Gecko/20100101 Thunderbird/24.2.0 MIME-Version: 1.0 To: Peter Gutmann , "tls@ietf.org" , "ietf-ssh@NetBSD.org" Subject: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups? References: <9A043F3CF02CD34C8E74AC1594475C7372388364@uxcn10-6.UoA.auckland.ac.nz> In-Reply-To: <9A043F3CF02CD34C8E74AC1594475C7372388364@uxcn10-6.UoA.auckland.ac.nz> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Peter Gutmann skrev 2014-03-08 02:21: > Mouse writes: > >>> Getting a hash of the byte string seems to be the easiest way to do >>> this. >> Not just computing it and comparing it against the value in RFC3526? > It depends what you're trying to verify. If the question is "are the values > given in RFC 2409/3526 correct?" then that's the way to do it (and thanks for > pointing out the issue with bc and pi :-). If the question is "does the byte > string I currently have in memory correspond to the data in the RFC" then > shelling out to Mathematica and bc isn't really an option, a SHA-1 hash for > quick verification seems the best way to go. The problem with calculating the hash of the internal representation, is that the hash will depend on the internal representation, which is prone to be implementation specific. Is it little endian or big endian? Is there a zero valued word in the most significant position or not? I think it is possible to run a relatively fast arithmetic test that will be dominated by the time it takes to perform a single modular exponentiation. If you got a big num libary, implementing an optimized formula for pi is relatively easy. You could implement a function that returns the prime p given the bit size n and small constant k, and let this function verify that k is the correct value. From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Sat Mar 8 03:40:50 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 598EB1A01E1 for ; Sat, 8 Mar 2014 03:40:50 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 9iCizILYx9IL for ; Sat, 8 Mar 2014 03:40:49 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 94C7B1A011E for ; Sat, 8 Mar 2014 03:40:49 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id C506814A2CF; Sat, 8 Mar 2014 11:40:42 +0000 (UTC) Delivered-To: ietf-ssh@NetBSD.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 0FD2614A2C8 for ; Sat, 8 Mar 2014 11:40:41 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id HRS5nRQGyHKn for ; Sat, 8 Mar 2014 11:40:40 +0000 (UTC) Received: from defiant.e-webshops.eu (defiant.e-webshops.eu [82.146.122.140]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 630E014A2C7 for ; Sat, 8 Mar 2014 11:40:39 +0000 (UTC) Received: from intrepid.roeckx.be (localhost [127.0.0.1]) by defiant.e-webshops.eu (Postfix) with ESMTP id 130A51C2151; Sat, 8 Mar 2014 11:21:43 +0100 (CET) Received: by intrepid.roeckx.be (Postfix, from userid 1000) id C72091FE018E; Sat, 8 Mar 2014 11:21:42 +0100 (CET) Date: Sat, 8 Mar 2014 11:21:42 +0100 From: Kurt Roeckx To: Mouse Cc: tls@ietf.org, ietf-ssh@NetBSD.org Subject: Re: [TLS] I can has SHA-1 hashes for RFC 2409/3526 MODP groups? Message-ID: <20140308102142.GA25856@roeckx.be> References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> User-Agent: Mutt/1.5.21 (2010-09-15) Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On Fri, Mar 07, 2014 at 06:18:11PM -0500, Mouse wrote: > > However, if you add 18 more 0s to the long string of them (which the > formatting makes it look likely got dropped in whatever produced the > weird line breaks above - if I add 18 more 0s and paste the first two > lines together, the result is exactly as long as the next five lines), > that _is_ 2^2048 - 2^1984 - 1 + (2^64 * 124476). That is, it's what > you get if you take pi to be 0. I suspect your bc didn't recognize the > character string "pi" and treated it as an unset variable or some such, > effectively replacing it with 0. If you want pi in bc, you need to start bc with the -l option and do: pi=4*a(1) Kurt From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Sat Mar 8 10:58:35 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E001C1A0143 for ; Sat, 8 Mar 2014 10:58:35 -0800 (PST) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id V30u5-MYa_yv for ; Sat, 8 Mar 2014 10:58:34 -0800 (PST) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 831521A0142 for ; Sat, 8 Mar 2014 10:58:33 -0800 (PST) Received: by mail.netbsd.org (Postfix, from userid 605) id 5878514A31F; Sat, 8 Mar 2014 18:58:26 +0000 (UTC) Delivered-To: ietf-ssh@NetBSD.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 87B4E14A319 for ; Sat, 8 Mar 2014 18:58:19 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id C3F0_PTGyfTQ for ; Sat, 8 Mar 2014 18:58:18 +0000 (UTC) Received: from co9outboundpool.messaging.microsoft.com (co9ehsobe005.messaging.microsoft.com [207.46.163.28]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 5FF7C14A317 for ; Sat, 8 Mar 2014 18:58:17 +0000 (UTC) Received: from mail217-co9-R.bigfish.com (10.236.132.239) by CO9EHSOBE036.bigfish.com (10.236.130.99) with Microsoft SMTP Server id 14.1.225.22; Sat, 8 Mar 2014 18:13:07 +0000 Received: from mail217-co9 (localhost [127.0.0.1]) by mail217-co9-R.bigfish.com (Postfix) with ESMTP id E3A41E00073; Sat, 8 Mar 2014 18:13:06 +0000 (UTC) X-Forefront-Antispam-Report: CIP:66.129.239.16;KIP:(null);UIP:(null);IPV:NLI;H:P-EMF02-SAC.jnpr.net;RD:none;EFVD:NLI X-SpamScore: 1 X-BigFish: VPS1(zz98dIe0eah1432Izz1f42h208ch1ee6h1de0h1fdah2073h2146h1202h1e76h2189h1d1ah1d2ah21bch1fc6h1082kzz1de098h1de097hz31h2a8h839hf0ah1288h12a5h12a9h12bdh12e5h137ah139eh13b6h1441h14ddh1504h1537h162dh1631h1758h1898h18e1h1946h19b5h1ad9h1b0ah1b2fh224fh1fb3h1d0ch1d2eh1d3fh1de2h1dfeh1dffh1e23h1fe8h1ff5h2218h2216h226dh22d0h24afh2327h2336h2438h2461h2487h24d7h2516h2545h255eh25cch25f6h2605h1155h) Received-SPF: softfail (mail217-co9: transitioning domain of juniper.net does not designate 66.129.239.16 as permitted sender) client-ip=66.129.239.16; envelope-from=mdb@juniper.net; helo=P-EMF02-SAC.jnpr.net ;SAC.jnpr.net ; Received: from mail217-co9 (localhost.localdomain [127.0.0.1]) by mail217-co9 (MessageSwitch) id 1394302383694623_28879; Sat, 8 Mar 2014 18:13:03 +0000 (UTC) Received: from CO9EHSMHS016.bigfish.com (unknown [10.236.132.234]) by mail217-co9.bigfish.com (Postfix) with ESMTP id 9A4F01EC0047; Sat, 8 Mar 2014 18:13:03 +0000 (UTC) Received: from P-EMF02-SAC.jnpr.net (66.129.239.16) by CO9EHSMHS016.bigfish.com (10.236.130.26) with Microsoft SMTP Server (TLS) id 14.16.227.3; Sat, 8 Mar 2014 18:13:03 +0000 Received: from magenta.juniper.net (172.17.27.123) by P-EMF02-SAC.jnpr.net (172.24.192.21) with Microsoft SMTP Server (TLS) id 14.3.146.0; Sat, 8 Mar 2014 10:13:02 -0800 Received: from eng-mail01.juniper.net (eng-mail01.juniper.net [172.17.28.114]) by magenta.juniper.net (8.11.3/8.11.3) with ESMTP id s28ID0V84269; Sat, 8 Mar 2014 10:13:00 -0800 (PST) (envelope-from mdb@juniper.net) Received: from eng-mail01.juniper.net (localhost [127.0.0.1]) by eng-mail01.juniper.net (Postfix) with ESMTP id EE8491148D; Sat, 8 Mar 2014 10:12:58 -0800 (PST) To: Kurt Roeckx , Peter Gutmann CC: Mouse , , Subject: Re: [TLS] I can has SHA-1 hashes for RFC 2409/3526 MODP groups? In-Reply-To: <20140308102142.GA25856@roeckx.be> References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> Comments: In-reply-to: Kurt Roeckx message dated "Sat, 08 Mar 2014 11:21:42 +0100." From: "Mark D. Baushke" X-Mailer: MH-E 8.2; nmh 1.2; GNU Emacs 22.1.1 X-Face: #8D_6URD2G%vC.hzU MIME-Version: 1.0 Content-Type: text/plain X-OriginatorOrg: juniper.net X-FOPE-CONNECTOR: Id%0$Dn%*$RO%0$TLS%0$FQDN%$TlsDn% Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Hi Kurt, You raise a good point. Folks with 'bc -l' should be able to verify the MODP groups. Kurt Roeckx writes: > On Fri, Mar 07, 2014 at 06:18:11PM -0500, Mouse wrote: > > > > However, if you add 18 more 0s to the long string of them (which the > > formatting makes it look likely got dropped in whatever produced the > > weird line breaks above - if I add 18 more 0s and paste the first two > > lines together, the result is exactly as long as the next five lines), > > that _is_ 2^2048 - 2^1984 - 1 + (2^64 * 124476). That is, it's what > > you get if you take pi to be 0. I suspect your bc didn't recognize the > > character string "pi" and treated it as an unset variable or some such, > > effectively replacing it with 0. > > If you want pi in bc, you need to start bc with the -l option and do: > pi=4*a(1) Yes. Of course, to get the same values as is used in the RFCs more fractional bits need to be calculated Using bc to calculate the group14 and group15 primes: $ bc -l scale=1000 /* should be enough for group 14 and group 15 */ obase=16 /* A function to return the largest integral value not greater than x */ define floor(x) { auto s s = scale scale = 0 x /= 1 /* round x down */ scale = s return (x) } pi=4*a(1) pi 3.243F6A8885A308D313198A2E03707344A4093822299F31D0082EFA98EC4E6C8945\ 2821E638D01377BE5466CF34E90C6CC0AC29B7C97C50DD3F84D5B5B54709179216D5\ D98979FB1BD1310BA698DFB5AC2FFD72DBD01ADFB7B8E1AFED6A267E96BA7C9045F1\ 2C7F9924A19947B3916CF70801F2E2858EFC16636920D871574E69A458FEA3F4933D\ 7E0D95748F728EB658718BCD5882154AEE7B54A41DC25A59B59C30D5392AF26013C5\ D1B023286085F0CA417918B8DB38EF8E79DCB0603A180E6C9E0E8BB01E8A3ED71577\ C1BD314B2778AF2FDA55605C60E65525F3AA55AB945748986263E8144055CA396A2A\ AB10B6B4CC5C341141E8CEA15486AF7C72E993B3EE1411636FBC2A2BA9C55D741831\ F6CE5C3E169B87931EAFD6BA336C24CF5C7A325381289586773B8F48986B4BB9AFC4\ BFE81B6628219361D809CCFB21A991487CAC605DEC8032EF845D5DE98575B1DC2623\ 02EB651B8823893E81D396ACC50F6D6FF383F442392E0B4482A484200469C8F04A9E\ 1F9B5E21C66842F6E96C9A670C9C61ABD388F06A51A0D2D8542F68960FA728AB5133\ A36EEF0B6C137A3B8 2^2048 - 2^1984 - 1 + 2^64 * (floor(pi * 2^1918) + 124476) /* group 14 */ FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020B\ BEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D\ 6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A89\ 9FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A\ 69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C\ 354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2\ EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA\ 051015728E5A8AACAA68FFFFFFFFFFFFFFFF 2^3072 - 2^3008 - 1 + 2^64 * (floor(2^2942 * pi) + 1690314) /* group 15 */ FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020B\ BEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D\ 6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A89\ 9FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A\ 69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C\ 354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2\ EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA\ 051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A\ 8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3\ D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE11757\ 7A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A93A\ D2CAFFFFFFFFFFFFFFFF They both compare exactly to rfc3526. To calculate the group 16 value, I need to add more digits to pi scale=4000 /* need more digits for group 16 */ pi=4*a(1) 2^4096 - 2^4032 - 1 + 2^64 * (floor(pi * 2^3966) + 240904) /* group 16 */ FFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD129024E088A67CC74020B\ BEA63B139B22514A08798E3404DDEF9519B3CD3A431B302B0A6DF25F14374FE1356D\ 6D51C245E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7EDEE386BFB5A89\ 9FA5AE9F24117C4B1FE649286651ECE45B3DC2007CB8A163BF0598DA48361C55D39A\ 69163FA8FD24CF5F83655D23DCA3AD961C62F356208552BB9ED529077096966D670C\ 354E4ABC9804F1746C08CA18217C32905E462E36CE3BE39E772C180E86039B2783A2\ EC07A28FB5C55DF06F4C52C9DE2BCBF6955817183995497CEA956AE515D2261898FA\ 051015728E5A8AAAC42DAD33170D04507A33A85521ABDF1CBA64ECFB850458DBEF0A\ 8AEA71575D060C7DB3970F85A6E1E4C7ABF5AE8CDB0933D71E8C94E04A25619DCEE3\ D2261AD2EE6BF12FFA06D98A0864D87602733EC86A64521F2B18177B200CBBE11757\ 7A615D6C770988C0BAD946E208E24FA074E5AB3143DB5BFCE0FD108E4B82D120A921\ 08011A723C12A787E6D788719A10BDBA5B2699C327186AF4E23C1A946834B6150BDA\ 2583E9CA2AD44CE8DBBBC2DB04DE8EF92E8EFC141FBECAA6287C59474E6BC05D99B2\ 964FA090C3A2233BA186515BE7ED1F612970CEE2D7AFB81BDD762170481CD0069127\ D5B05AA993B4EA988D8FDDC186FFB7DC90A6C08F4DF435C934063199FFFFFFFFFFFF\ FFFF The above was calculated using GNU bc version 1.06. -- Mark From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Tue Mar 11 16:33:49 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BBBC81A088C for ; Tue, 11 Mar 2014 16:33:49 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 0.853 X-Spam-Level: X-Spam-Status: No, score=0.853 tagged_above=-999 required=5 tests=[BAYES_50=0.8, J_CHICKENPOX_71=0.6, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id vHSKWyvisNSx for ; Tue, 11 Mar 2014 16:33:45 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id C478F1A0877 for ; Tue, 11 Mar 2014 16:33:44 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 0414714A23B; Tue, 11 Mar 2014 23:33:37 +0000 (UTC) Delivered-To: ietf-ssh@NetBSD.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 46BA914A215 for ; Tue, 11 Mar 2014 23:33:26 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id BbU5oBJYEIpb for ; Tue, 11 Mar 2014 23:33:25 +0000 (UTC) Received: from che.mayfirst.org (che.mayfirst.org [209.234.253.108]) by mail.netbsd.org (Postfix) with ESMTP id 2C57F14A20F for ; Tue, 11 Mar 2014 23:33:24 +0000 (UTC) Received: from [10.70.10.55] (unknown [38.109.115.130]) by che.mayfirst.org (Postfix) with ESMTPSA id 45049F984; Tue, 11 Mar 2014 18:15:05 -0400 (EDT) Message-ID: <531F8ADF.3060002@fifthhorseman.net> Date: Tue, 11 Mar 2014 18:14:55 -0400 From: Daniel Kahn Gillmor User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.2.0 MIME-Version: 1.0 To: IETF TLS WG , ietf-ssh@NetBSD.org Subject: MODP group modulus derivation [was: Re: [TLS] I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> In-Reply-To: <42833.1394302378@eng-mail01.juniper.net> X-Enigmail-Version: 1.6 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="hAgHuKgrHmI2tcAfN23JFTv8b2JR1ekqH" Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --hAgHuKgrHmI2tcAfN23JFTv8b2JR1ekqH Content-Type: multipart/mixed; boundary="------------080208080801050603010503" This is a multi-part message in MIME format. --------------080208080801050603010503 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 03/08/2014 01:12 PM, Mark D. Baushke wrote: > You raise a good point. Folks with 'bc -l' should be able to verify the= > MODP groups. The k-bit MODP discrete-log moduli is formulated as the smallest safe-prime that meets the form: 2^k - 2^(k-64) - 1 + 2^64 * { [2^(k-130) pi] + N } where N is a positive integer. More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of pi, followed by 64 more bits of 0xFF. I don't know why this sequence was selected. Does anyone have any pointers to reasons you might want the modulus structured this way? Given a bit-length k, The attached python program tests all integers N in sequence, stopping at the first safe-prime. For example: 0 dkg@alice:~$ python3 ./gen-modp.py 768 searching for 768-bit safe-prime modulus, starting at: FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 E485B576 625E7EC6 F44C42E9 A637ED6B FFFFFFFF FFFFFFFF added 0x248b6 * 2^64 (decimal: 149686 * 2^64) The prime is: 2^768 - 2^704 - 1 + 2^64 * { [2^638 pi] + 149686 } FFFFFFFF FFFFFFFF C90FDAA2 2168C234 C4C6628B 80DC1CD1 29024E08 8A67CC74 020BBEA6 3B139B22 514A0879 8E3404DD EF9519B3 CD3A431B 302B0A6D F25F1437 4FE1356D 6D51C245 E485B576 625E7EC6 F44C42E9 A63A3620 FFFFFFFF FFFFFFFF 0 dkg@alice:~$ Thus far, I've used it to generate the moduli for these groups: * 768-bit (MODP 1) * 1024-bit (MODP 2) * 1536-bit (MODP 5) * 2048-bit (MODP 14) * 3072-bit (MODP 15) i haven't yet generated these (mainly due to time): * 4096-bit (MODP 16) * 6144-bit (MODP 17) * 8192-bit (MODP 18) Regards, --dkg --------------080208080801050603010503 Content-Type: text/x-python; name="gen-modp.py" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline; filename="gen-modp.py" #!/usr/bin/python # Author: Daniel Kahn Gillmor # Date: 2014-03-11 # derive p for the default groups in RFC 3526 and RFC 5996 # these RFCs use a particular approach to derive the prime modulus, # based only on the size of the prime desired, and on the digits of pi. # this code performs the same search pattern and verifies the result. # Usage:=20 # $ python3 gen-modp.py 1024 # this will generate the 1024-bit modulus found in RFC 5996. import sys import gmpy2 def breakup(s,k): '''return string s broken into chunks of size k''' return (s[0+n:k+n] for n in range(0,len(s),k)) def displayhex(mpz,stream): '''write an mpz to stream in the form preferred by the MODP RFC's''' h =3D hex(mpz)[2:].upper() # strip leading 0x linelen =3D 48 if len(h) =3D=3D 6144//4: linelen +=3D 8 # section 6 of RFC 3526 is unusually-formatted for x in breakup(h,linelen): for y in breakup(x,8): stream.write(" " + y) stream.write("\n") def t_pi(n): '''return an mpz containing the first n bits of pi''' gmpy2.get_context().precision=3Dn+1 return gmpy2.mpz(gmpy2.floor((gmpy2.mpz(1) << (n-2)) * gmpy2.cons= t_pi(n+1))) def checkanswer(bitsize,inc): '''Given a number of bits and an selected offset, verify that the expected result of the MODP modulus selection scheme is a safe prime. We're using probabilistic primality testing here, but leaning hard on the test, making sure it's expensive and much more thorough than the default tests used during selection. ''' one =3D gmpy2.mpz(1) val =3D (one << bitsize) - (one << (bitsize-64)) - one + \ ((one<<64)* (t_pi(bitsize - 128) + inc)) if not (gmpy2.is_prime(val, bitsize) and \ gmpy2.is_prime((val-1)//2,bitsize)): raise Exception("expensive primality tests contradicted "+\ "the cheap ones!") print("The prime is: 2^%d - 2^%d - 1 + 2^64 * { [2^%d pi] + %d }"%\ (bitsize, bitsize-64, bitsize-(64+66), inc)) displayhex(val, sys.stdout) def search(bitsize): '''search for a prime with bitsize bits, using the pattern establishe= d by the MODP RFC's. ''' bits =3D gmpy2.mpz(0xffffffffffffffff) # 64 bits of 0xff # the remaining bits of pi # 64 bits of 0xff # then count up until we find a prime base =3D (bits << (bitsize-64)) + (t_pi(bitsize-128) << 64) + bits print("searching for %d-bit safe-prime modulus, starting at:"%(bitsiz= e,)) displayhex(base,sys.stdout) inc =3D 1 # initial offset started to clear the middle bits for pi while not gmpy2.is_prime(base) \ or not gmpy2.is_prime((base-1)>>1): if (inc % 17) =3D=3D 1: sys.stdout.write("\radding 0x%x * 2^64"%(inc)) inc +=3D 1 base +=3D 2**64 sys.stdout.write("\radded 0x%x * 2^64 (decimal: %d * 2^64)\n"%\ (inc,inc)) return inc if sys.argv.__len__() > 1: target =3D int(sys.argv[1]) else: target =3D 768 inc =3D search(target) checkanswer(target,inc) --------------080208080801050603010503-- --hAgHuKgrHmI2tcAfN23JFTv8b2JR1ekqH Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 Comment: Using GnuPG with Icedove - http://www.enigmail.net/ iQJ8BAEBCgBmBQJTH4rfXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRFQjk2OTEyODdBN0FEREUzNzU3RDkxMUVB NTI0MDFCMTFCRkRGQTVDAAoJEKUkAbEb/fpcEOoQAOhJcRyP/9gOVqGLdzU4NJ2C +oJL5QZO6YXRMHN3AAjmX3iA7ccVx2xCNf99+vrleh11kC7lagZ3yqN2ZjufOpUg 0Rd3lg3n4FiOfjksqP36D8gDfoRsZmQgLA7qS+MNd8W80o3j3DR3uoyNZgtEYdMK natwJnSx6gVm2FzeU3BAe+AVFJyjVEPj7AypjvbbI/C2qajlD27vh/d0Dj9CECCe SGNcfPBQICNL/Pqr0xZbC/JUfvJ0lviCQkU1eJ5OTExa5P+6cVLMdN3oEINr7C7C TO7twz3OQgCfDBEM8DOMSGBq+3O6L8dOjFPb734sNBnFYggeAdpRlBI1sRxo2r5m eNq87LCFpX5YrWgL6KEXwmHhyDED8jRigs9OhDink2pQsXx3hLAodSWAy7VSLj+g fPp0dIO3flKicoIyEzt7LYxr3/QGtFqpv0H0+gJ6OhNpWpGWzT0ZiAEIyx1QLGoN mi0b/WnMEqEX6AvEzdUU3QcucxMOiJFZXqZcsuoAtu6H8OUPElG8Prw9ygWuT8g1 4iKtScMbUzMcBUfXVRIQaFcY5L3X0/o0nbhGBvWiiDRBbVG0zQeLQoqQ1uwvcKN9 /1MFCOyAFrUxRj7TDQECzrvgYAmXoYc7Mk9RVKPbrHjzaRXG5LjvAvPDMebsnDqA 7zSjlCDJfAnFM7I7/kX4 =1yQN -----END PGP SIGNATURE----- --hAgHuKgrHmI2tcAfN23JFTv8b2JR1ekqH-- From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Tue Mar 11 19:18:52 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 3A2C51A08D2 for ; Tue, 11 Mar 2014 19:18:52 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.147 X-Spam-Level: X-Spam-Status: No, score=-2.147 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id IBkfnpbYUIWP for ; Tue, 11 Mar 2014 19:18:50 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 615241A08CE for ; Tue, 11 Mar 2014 19:18:50 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id C961414A2A8; Wed, 12 Mar 2014 02:18:42 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 71FC914A291 for ; Wed, 12 Mar 2014 02:18:40 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id NOafPCgJ5zXK for ; Wed, 12 Mar 2014 02:18:39 +0000 (UTC) Received: from vsp4.ballou.se (vsp4.ballou.se [91.189.40.102]) by mail.netbsd.org (Postfix) with SMTP id 5650A14A282 for ; Wed, 12 Mar 2014 02:18:38 +0000 (UTC) Received: from nmail1.ballou.se (unknown [10.0.0.116]) by vsp4.ballou.se (Halon Mail Gateway) with ESMTP; Wed, 12 Mar 2014 02:16:12 +0100 (CET) Received: from [192.168.0.195] (c-a2c1e555.06-134-73746f39.cust.bredbandsbolaget.se [85.229.193.162]) (Authenticated sender: henrick@streamsec.se) by nmail1.ballou.se (Postfix) with ESMTPSA id 4EDF81E05E; Wed, 12 Mar 2014 02:18:19 +0100 (CET) Message-ID: <531FB5DC.1010001@streamsec.se> Date: Wed, 12 Mar 2014 02:18:20 +0100 From: =?UTF-8?B?SGVucmljayBIZWxsc3Ryw7Zt?= Reply-To: henrick@streamsec.se User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0 MIME-Version: 1.0 To: Daniel Kahn Gillmor , IETF TLS WG , ietf-ssh@NetBSD.org Subject: Re: MODP group modulus derivation [was: Re: [TLS] I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> In-Reply-To: <531F8ADF.3060002@fifthhorseman.net> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On 2014-03-11 23:14, Daniel Kahn Gillmor wrote: > More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of > pi, followed by 64 more bits of 0xFF. I don't know why this sequence > was selected. Does anyone have any pointers to reasons you might want > the modulus structured this way? - If the least significant word of the modulus equals 2^w-1, Montgomery reduction becomes more efficient. - If the most significant word of the modulus equals 2^w-1, school-book reduction and Barrett reduction becomes more efficient. - Pi usually plays the role of a "nothing-up-my-sleeve" value. If a random value had been chosen, there would have been no easy way to verify that a specially crafted value hadn't been chosen. For instance, it is possible to generate a prime, such that the discrete logarithm of selected smooth numbers becomes to known to the entity generating the prime, and that would make the discrete logarithm problem easier for that entity. > > i haven't yet generated these (mainly due to time): > > * 4096-bit (MODP 16) > * 6144-bit (MODP 17) > * 8192-bit (MODP 18) Python is likely too slow for this. Generating the 8192 bit prime takes a couple of hours on a contemporary PC using reasonably optimized native code. From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Tue Mar 11 20:56:32 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 046531A08DB for ; Tue, 11 Mar 2014 20:56:32 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.546 X-Spam-Level: X-Spam-Status: No, score=-2.546 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id m1KgNBmQPVDj for ; Tue, 11 Mar 2014 20:56:30 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id EC3F71A08B0 for ; Tue, 11 Mar 2014 20:56:28 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 9753714A251; Wed, 12 Mar 2014 03:56:20 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 2821F14A24F for ; Wed, 12 Mar 2014 03:56:16 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id WEKLbJWtIh1T for ; Wed, 12 Mar 2014 03:56:15 +0000 (UTC) Received: from mail-yh0-x231.google.com (mail-yh0-x231.google.com [IPv6:2607:f8b0:4002:c01::231]) (using TLSv1 with cipher AES128-SHA (128/128 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 464E514A24D for ; Wed, 12 Mar 2014 03:56:15 +0000 (UTC) Received: by mail-yh0-f49.google.com with SMTP id z6so9594390yhz.8 for ; Tue, 11 Mar 2014 20:56:14 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:in-reply-to:references:date:message-id:subject:from:to :cc:content-type:content-transfer-encoding; bh=2JpMOyQ5+ksDdHdx4VjwDgb/w1a52n75ocicKPPxLqY=; b=ysQLnopVlb56+LeAEvOuD7NtrlkBEsxQ2LQ6kJKrNr9cIFsA9VWEsxnYbMuM9bKd2r WMCi2QXLAKO4ZO8FDFLBWegAsLo+LQdRMkvFWLtux+shlsyHI19DM6rij8xhb1lE8/EY o/rZjB6Ifqe3MR/07dvK0ZUpPgofbdoGKZYaLALpeLumSECJEFs0HMJDJF99BrpIlnPC w/VQMypx9EJZoJMELQ2sAoTOWU3FvXnr8ej2MygMvyuHoLNRHgdoMJRnPceajdUHVjxI MV/1gM/rb91YMXIJEr5/flT5d/Nr2inLPG35sr1PSczbCisRV/joAdawCufNrPsn/ziv U2TQ== MIME-Version: 1.0 X-Received: by 10.236.139.70 with SMTP id b46mr14031026yhj.63.1394596574379; Tue, 11 Mar 2014 20:56:14 -0700 (PDT) Received: by 10.170.80.214 with HTTP; Tue, 11 Mar 2014 20:56:14 -0700 (PDT) In-Reply-To: <531FB5DC.1010001@streamsec.se> References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> <531FB5DC.1010001@streamsec.se> Date: Tue, 11 Mar 2014 20:56:14 -0700 Message-ID: Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] From: Watson Ladd To: henrick@streamsec.se Cc: Daniel Kahn Gillmor , IETF TLS WG , ietf-ssh@netbsd.org Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On Tue, Mar 11, 2014 at 6:18 PM, Henrick Hellstr=C3=B6m wrote: > > On 2014-03-11 23:14, Daniel Kahn Gillmor wrote: >> >> More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of >> pi, followed by 64 more bits of 0xFF. I don't know why this sequence >> was selected. Does anyone have any pointers to reasons you might want >> the modulus structured this way? > > > - If the least significant word of the modulus equals 2^w-1, Montgomery r= eduction becomes more efficient. > - If the most significant word of the modulus equals 2^w-1, school-book r= eduction and Barrett reduction becomes more efficient. > - Pi usually plays the role of a "nothing-up-my-sleeve" value. If a rando= m value had been chosen, there would have been no easy way to verify that a= specially crafted value hadn't been chosen. For instance, it is possible t= o generate a prime, such that the discrete logarithm of selected smooth num= bers becomes to known to the entity generating the prime, and that would ma= ke the discrete logarithm problem easier for that entity. > > >> >> i haven't yet generated these (mainly due to time): >> >> * 4096-bit (MODP 16) >> * 6144-bit (MODP 17) >> * 8192-bit (MODP 18) > > > Python is likely too slow for this. Generating the 8192 bit prime takes a= couple of hours on a contemporary PC using reasonably optimized native cod= e. A few hours? The trick is to sieve: the numbers for various N are in an arithmetic progression with a=3D2^64. As a result, you can determine which N are possible because of small prime obstructions, thus decreasing the amount of work to be done. In fact, I think your first N is entirely determined by considerations modulo the primes less than 100. Secondly look at (p-1)/2=3Dq instead. If this is known prime determining if 2*q+1 is prime is quick using Pocklington's Theorem: you don't need to do the extensive primality testing. Sincerely, Watson Ladd > > > _______________________________________________ > TLS mailing list > TLS@ietf.org > https://www.ietf.org/mailman/listinfo/tls --=20 "Those who would give up Essential Liberty to purchase a little Temporary Safety deserve neither Liberty nor Safety." -- Benjamin Franklin From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 00:47:34 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id BCB221A0900 for ; Wed, 12 Mar 2014 00:47:34 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id TCyxZ1aquFJP for ; Wed, 12 Mar 2014 00:47:33 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 57CF51A08EB for ; Wed, 12 Mar 2014 00:47:33 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 6925014A19A; Wed, 12 Mar 2014 07:47:25 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: by mail.netbsd.org (Postfix, from userid 1347) id 0AE5914A185; Wed, 12 Mar 2014 07:47:25 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id DD1BB14A27E for ; Wed, 12 Mar 2014 00:25:20 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id ifnGngxy3v9y for ; Wed, 12 Mar 2014 00:25:20 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 9635014A277 for ; Wed, 12 Mar 2014 00:25:15 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1394583920; x=1426119920; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=PqX/Ryv0hh3BgYugDTtcwd5Mxw8zZZGb8225ZJ+eXgg=; b=K57fWaUOR77epENVVAxP6V11zO4yxL4tLCfJivkm5OckoXy9GQ06N8x7 TxvgBsHOD5vH9xrSlHqv7ugl4SjZsxbpcHLQzGSSlWO9YdtvTIUHtGe+T S9L0joUM8QeUlwVCYAfDKXwl7f50wwmVIflpwAZPO5b5nygvWaam8aPAa E=; X-IronPort-AV: E=Sophos;i="4.97,634,1389697200"; d="scan'208";a="238959174" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.106 - Outgoing - Outgoing Received: from uxchange10-fe2.uoa.auckland.ac.nz ([130.216.4.106]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 12 Mar 2014 13:25:14 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe2.UoA.auckland.ac.nz ([130.216.4.106]) with mapi id 14.03.0174.001; Wed, 12 Mar 2014 13:25:13 +1300 From: Peter Gutmann To: "" , "ietf-ssh@netbsd.org" Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] Thread-Topic: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] Thread-Index: Ac89iYieoDktMLvTRCu1CZHjC2IAVQ== Date: Wed, 12 Mar 2014 00:25:12 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C737238A20F@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Daniel Kahn Gillmor writes:=0A= =0A= >More colloquially, this is: 64 bits of 0xFF, followed by (k-128) bits of p= i,=0A= >followed by 64 more bits of 0xFF. I don't know why this sequence was=0A= >selected. Does anyone have any pointers to reasons you might want the=0A= >modulus structured this way?=0A= =0A= The prime for this group was selected to have certain properties. The = high=0A= order 64 bits are forced to 1. This helps the classical remainder=0A= algorithm, because the trial quotient digit can always be taken as the = high=0A= order word of the dividend, possibly +1. The low order 64 bits are for= ced=0A= to 1. This helps the Montgomery-style remainder algorithms, because th= e=0A= multiplier digit can always be taken to be the low order word of the=0A= dividend. The middle bits are taken from the binary expansion of pi. = This=0A= guarantees that they are effectively random, while avoiding any suspici= on=0A= that the primes have secretly been selected to be weak.=0A= =0A= The prime is chosen to be a Sophie-Germain prime (i.e., (P-1)/2 is also= =0A= prime), to have the maximum strength against the square-root attack. T= he=0A= starting trial numbers were repeatedly incremented by 2^64 until suitab= le=0A= primes were located.=0A= =0A= Because this prime is congruent to 7 (mod 8), 2 is a quadratic residue.= =0A= All powers of 2 will also be quadratic residues. This prevents an oppon= ent=0A= from learning the low order bit of the Diffie-Hellman exponent. Using = 2 as=0A= a generator is efficient for some modular exponentiation algorithms. [= Note=0A= that 2 is technically not a generator in the number theory sense, becau= se=0A= it omits half of the possible residues mod P. From a cryptographic=0A= viewpoint, this is a virtue.]=0A= =0A= This is from an early Oakley draft draft-ietf-ipsec-isakmp-oakley-03.txt th= at=0A= references another Oakley draft draft-ietf-ipsec-oakley-01.txt which, howev= er,=0A= doesn't actually contain the text quoted above. So I guess the reference= =0A= would be [Citation needed ^ 2] or [Apocryphal ^ 2].=0A= =0A= (Oh, and if anyone feels like confirming the SHA-1 hashes of the primes I= =0A= posted last week....).=0A= =0A= Peter.=0A= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 02:53:45 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 7DECF1A0944 for ; Wed, 12 Mar 2014 02:53:45 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.147 X-Spam-Level: X-Spam-Status: No, score=-2.147 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id E46ctIZyFmGj for ; Wed, 12 Mar 2014 02:53:39 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 7243B1A0930 for ; Wed, 12 Mar 2014 02:53:39 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 3546114A247; Wed, 12 Mar 2014 09:53:33 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id E762714A227 for ; Wed, 12 Mar 2014 09:53:30 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id tdz9l1wDUV1z for ; Wed, 12 Mar 2014 09:53:30 +0000 (UTC) Received: from vsp4.ballou.se (vsp4.ballou.se [91.189.40.102]) by mail.netbsd.org (Postfix) with SMTP id CB9D314A1FF for ; Wed, 12 Mar 2014 09:53:28 +0000 (UTC) Received: from nmail1.ballou.se (unknown [10.0.0.116]) by vsp4.ballou.se (Halon Mail Gateway) with ESMTP; Wed, 12 Mar 2014 10:51:18 +0100 (CET) Received: from [192.168.0.195] (c-a2c1e555.06-134-73746f39.cust.bredbandsbolaget.se [85.229.193.162]) (Authenticated sender: henrick@streamsec.se) by nmail1.ballou.se (Postfix) with ESMTPSA id 3ED6D1E061; Wed, 12 Mar 2014 10:53:26 +0100 (CET) Message-ID: <53202E8D.9090403@streamsec.se> Date: Wed, 12 Mar 2014 10:53:17 +0100 From: =?UTF-8?B?SGVucmljayBIZWxsc3Ryw7Zt?= Reply-To: henrick@streamsec.se User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0 MIME-Version: 1.0 To: Watson Ladd CC: Daniel Kahn Gillmor , IETF TLS WG , ietf-ssh@netbsd.org Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> <531FB5DC.1010001@streamsec.se> In-Reply-To: Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On 2014-03-12 04:56, Watson Ladd wrote: > A few hours? The trick is to sieve: the numbers for various N are in > an arithmetic progression with a=2^64. As a result, you can determine > which N are possible because of small prime obstructions, thus > decreasing the amount of work to be done. In fact, I think your first > N is entirely determined by considerations modulo the primes less than > 100. > > Secondly look at (p-1)/2=q instead. If this is known prime determining > if 2*q+1 is prime is quick using Pocklington's Theorem: you don't need > to do the extensive primality testing. Exactly, have you tried this? For the 8192 bit prime, you are to eliminate 4,743,158 candidates. Suppose: - you are using a double sieve on both primes that eliminates all but 0.6-0.7% of the candidates, - you are doing the Fermat test of the Pocklington criterion first, and this eliminates all but 1-2% of the remaining candidates, then this means your search will still be dominated by some 300,000 modular exponentiations with a 8192 bit modulus and with 8191 bit exponents. Let's say a reasonably optimized implementation performs such an exponentiation in 400ms on a contemporary PC. This leaves you with an expected running time of 20 min. From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 07:08:52 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id ED0841A087C for ; Wed, 12 Mar 2014 07:08:51 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.147 X-Spam-Level: X-Spam-Status: No, score=-2.147 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id oPZpZHfvcwcb for ; Wed, 12 Mar 2014 07:08:47 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 0EFCC1A06B2 for ; Wed, 12 Mar 2014 07:08:47 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 91C7D14A23E; Wed, 12 Mar 2014 14:08:38 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 243C914A242 for ; Wed, 12 Mar 2014 14:08:19 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id EBqhrKI0fE6o for ; Wed, 12 Mar 2014 14:08:17 +0000 (UTC) Received: from bacon.lysator.liu.se (vindbrygga.lysator.liu.se [IPv6:2001:6b0:17:f0a0::de]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 5CD6514A23F for ; Wed, 12 Mar 2014 14:08:15 +0000 (UTC) Received: from bacon.lysator.liu.se (localhost [127.0.0.1]) by bacon.lysator.liu.se (8.14.5+Sun/8.14.5) with ESMTP id s2CE86Fh028845; Wed, 12 Mar 2014 15:08:06 +0100 (MET) Received: (from nisse@localhost) by bacon.lysator.liu.se (8.14.5+Sun/8.14.5/Submit) id s2CE850C028844; Wed, 12 Mar 2014 15:08:05 +0100 (MET) X-Authentication-Warning: bacon.lysator.liu.se: nisse set sender to nisse@lysator.liu.se using -f From: nisse@lysator.liu.se (Niels =?iso-8859-1?Q?M=F6ller?=) To: henrick@streamsec.se Cc: Watson Ladd , Daniel Kahn Gillmor , IETF TLS WG , ietf-ssh@netbsd.org Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> <531FB5DC.1010001@streamsec.se> <53202E8D.9090403@streamsec.se> Date: Wed, 12 Mar 2014 15:08:05 +0100 In-Reply-To: <53202E8D.9090403@streamsec.se> ("Henrick =?iso-8859-1?Q?Hell?= =?iso-8859-1?Q?str=F6m=22's?= message of "Wed, 12 Mar 2014 10:53:17 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (usg-unix-v) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Henrick Hellström writes: >> Secondly look at (p-1)/2=q instead. If this is known prime determining >> if 2*q+1 is prime is quick using Pocklington's Theorem: you don't need >> to do the extensive primality testing. > > Exactly, have you tried this? I couldn't resist, so I have now tried that. Below is a lite program to search for strong primes of the given form. It generates a 4096-bit prime in about 30s on my office machine (an intel core i5). I haven't had the patience to let it complete search for the 8192 prime. Some comments: 1. This is a quick hack, not thoroughly tested or profiled, etc. 2. It may be advantageous to use an even larger prime table for the sieving. Current code overflows somewhere if it is made substantially larger, though. Generating the prime table is more or less instantaneous. 3. The 8192-bit prime definitely seems a bit expensive to generate. 4. I let the pari/gp compute the pi approximation for me. The program could be made more self-contained if one adds some suitable function for computing pi to arbitrary precision, but I'm not really familiar with that problem. Regards, /Niels /* Copyright (C) 2014 Niels Möller This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with this program. If not, see . */ #include #include #include #include #include #include static void * xalloc (size_t size) { void *p = malloc (size); if (!p) { fprintf (stderr, "Memory exhausted.\n"); abort(); } return p; } static void * xrealloc (void *p, size_t size) { p = realloc (p, size); if (!p) { fprintf (stderr, "Memory exhausted.\n"); abort(); } return p; } struct prime_info { uint32_t p; /* An odd prime. */ uint32_t inv; /* p^{-1} mod 2^32 */ uint32_t limit; /* floor ((2^32-1) / p) */ }; static struct prime_info *primes; static unsigned nprimes; #define DIVISIBLE_P(x, i) ((x) * primes[i].inv <= primes[i].limit) static uint32_t binvert(uint32_t a) { unsigned char tab[8] = { 1, 11, 13, 7, 9, 3, 5, 15 }; uint32_t x = tab[(a >> 1) & 7]; /* 4-bit inverse */ x = 2*x - a*x*x; /* 8 bits */ x = 2*x - a*x*x; /* 16 bits */ x = 2*x - a*x*x; /* 32 bits */ assert (a*x == 1); return x; } static void init_table (unsigned limit) { /* Number of odd numbers in the range 3 <= j < limit */ unsigned sieve_size = limit/2-1; char *sieve = xalloc (sieve_size); unsigned table_size = 0; unsigned i; primes = NULL; nprimes = 0; memset (sieve, 1, sieve_size); for (i = 0; i < sieve_size; i++) { unsigned p = 3 + 2*i; unsigned j; if (sieve[i]) { /* fprintf (stderr, "%u\n", p); */ if (nprimes <= table_size) { table_size = 50 + 3*table_size/2; primes = realloc (primes, table_size); } primes[nprimes].p = p; primes[nprimes].inv = binvert(p); primes[nprimes].limit = (~(uint32_t) 0) / p; nprimes++; } /* Clear elements corrsponding to p^2, (p+2)^p, ... */ for (j = (p*p-3)/2; j < sieve_size; j += p) sieve[j] = 0; } free (sieve); } /* Find the first strong prime in the sequence start + k step */ void next_strong_prime(mpz_t r, const mpz_t start, const mpz_t step) { mpz_t t, q, p, pm1, h; uint32_t *qmod = xalloc (nprimes * sizeof(*qmod)); uint32_t *hmod = xalloc (nprimes * sizeof(*hmod)); unsigned i; mpz_inits (t, q, p, pm1, h, NULL); /* Some other variants are possible, but exclude them, for simplicity */ assert (mpz_odd_p (start)); assert (mpz_even_p (step)); mpz_gcd (t, start, step); assert (mpz_cmp_ui (t, 1) == 0); mpz_sub_ui (q, start, 1); mpz_fdiv_q_2exp (q, q, 1); mpz_fdiv_q_2exp (h, step, 1); for (i = 0; i < nprimes; i++) hmod[i] = mpz_fdiv_ui (h, primes[i].p); for (;;) { /* New q, recompute qmod */ for (i = 0; i < nprimes; i++) qmod[i] = mpz_fdiv_ui (q, primes[i].p); /* Limit to avoid overflow in i * hmod[j] */ for (i = 0; i < 100000; i++) { unsigned j; for (j = 0; j < nprimes; j++) { if (DIVISIBLE_P(qmod[j] + i * hmod[j], j)) /* q not prime */ goto not_prime; if (DIVISIBLE_P(2*qmod[j] + 1 + 2*i * hmod[j], j)) /* p not prime */ goto not_prime; } fprintf (stderr, "."); mpz_addmul_ui (q, h, i); mpz_mul_2exp (pm1, q, 1); mpz_add_ui (p, pm1, 1); /* Since q is updated, we need to reset i and update qmod */ for (j = 0; j < nprimes; j++) qmod[j] = (qmod[j] + i * hmod[j]) % primes[j].p; i = 0; /* First check if q prime implies p prime. By pocklington, check that gcd (a^2-1, p) = 1 and a^{2q} = 1 (mod p). Need use only a == 2, and then we already know that a^2-1 = 3 doesn't have any common factor with p. */ mpz_set_ui (t, 2); mpz_powm (t, t, q, p); /* If t = +/- 1 (mod p), then t^2 = 1, and the conditions of Pocklingtons's theorem (except q prime, which remain to be checked) are satisfied. On the other hand, if p and q are indeed prime, then 1 or -1 are the only possibilities, since t^2 = a^{p-1} = 1 (mod p), and those values are the only square roots of 1. */ if (mpz_cmp_ui (t, 1) != 0 && mpz_cmp (t, pm1) != 0) goto not_prime; fprintf (stderr, "p"); if (!mpz_millerrabin (q, 25)) goto not_prime; assert (mpz_probab_prime_p (p, 25)); fprintf (stderr, "pq\n"); mpz_swap (r, p); mpz_clears (t, q, p, pm1, h, NULL); free (hmod); free (qmod); return; not_prime: /* Go on with the same i and q */ ; } /* Can this ever happen? */ mpz_addmul_ui (q, h, i); fprintf (stderr, "100000 candidates passed trial division!\n"); } } int main (int argc, char **argv) { mpz_t pi8192, start, step, t, p; int bits; int limit = 1000000; if (argc < 2) { fprintf (stderr,"%s BITS [SIEVE-LIMIT]\n", argv[0]); return EXIT_FAILURE; } bits = atoi(argv[1]); if (bits < 256 || bits > 8192) { fprintf (stderr,"Supported range is 256 <= bits < 8192.\n"); return EXIT_FAILURE; } if (argc > 2) { limit = atoi(argv[2]); if (limit < 4) { fprintf (stderr,"Invalid prime limit.\n"); return EXIT_FAILURE; } } init_table(limit); fprintf (stderr, "Using %u primes for sieving, largest p = %u\n", nprimes, primes[nprimes-1].p); mpz_inits (pi8192, start, step, t, p, NULL); /* floor (pi * 2^8192), computed with pari/gp. This is an 8194 bit number */ mpz_set_str (pi8192, "342668632977872056340614340318593589633845496407221537975716" "613737152546230132865696034849115540419392405119782364448996" "505597009061206839355038690511597649633340755295662641609317" "535642924345851483170828622195425552862989984357380546470618" "654558998494810401062770045070958319118968772694396124916431" "894580767686315880694138861428875902873600542294826287748558" "777680794805812784463450507747144885813404423833320387798321" "609280015466841325521574345612804300925224268961852838014727" "344949392988773343665477596160680355250188118765396205271825" "594335340262310201378513530164474118131690724342410799910757" "546982847641291056024097727491901066776286401345290418249625" "628084349896086834732113313412019501787434146151912994099903" "795562822901556466065108423731653397934665628418225503906500" "252356756723136478156580557983552276992132926102607206902926" "217226186459755888047793134565096032547470753739485581485056" "095310312774412642091527392486496373093667048791992749203017" "039714338536895459352056225848086680604116795009774640833217" "634173864865403767984673414411303165787683355096108212088449" "911140581907950288312790601048394648396324285541310288154248" "299687810226823038493790254875059185044994880417764356982840" "836688145748032677215052979431605921845872542983666091618301" "641191123769382721257794537529591295620218822973870974507625" "710916011007688849347790863162497296922421716445647812915537" "174656134053117238096786067011739714153581530618764175406523" "316433003785370745957635127014688173775323182910793894295533" "869774970638119508426058911918833814428165195037324835873478" "264560759508465057903722354035637978838385867006178927628223" "655893247618439468688098957702197415152483332250099523049205" "947113206854728848346101557957368387613667773778399604898871" "571620512445391665708436224753527427390770571921354058146861" "534703545990059875592521055483476922407124171344793745585445" "612078729092110740281827121644569208704341570355808361384144" "320068653876547846047724572021904389025572441127188782597462" "975206221252835136986819772656964303920606775754918430878535" "831653872047705625068521848678547523189492202180161565293546" "004893947202674258029340791722950503743099899657901284673761" "082932857148614112547296837932346608390996266386438042203034" "975635130970578410146576920597437945752613183601468824949930" "014430184646230304464605951116975119907446615541881480270560" "054980165635722725085125496591712178571547448110006296573138" "030681065709805770745255837670620283490202933751846093959476" "8886090", 10); mpz_setbit (step, 64); mpz_sub_ui (t, step, 1); mpz_mul_2exp (start, t, bits - 64); mpz_add (start, start, t); mpz_fdiv_q_2exp (t, pi8192, (8194 + 128 - bits)); assert (mpz_sizeinbase (t, 2) == bits - 128); mpz_mul_2exp (t, t, 64); mpz_add (start, start, t); next_strong_prime (p, start, step); mpz_sub (t, p, start); mpz_fdiv_q_2exp (t, t, 64); gmp_printf ("p = 0x%Zx\nt = %Zd\n", p, t); mpz_clears (pi8192, start, step, t, p, NULL); free (primes); return EXIT_SUCCESS; } -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 10:39:17 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 6F0A51A074E for ; Wed, 12 Mar 2014 10:39:17 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id xYYk6oHx4anu for ; Wed, 12 Mar 2014 10:39:15 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id EDEC01A048A for ; Wed, 12 Mar 2014 10:39:14 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 7336514A262; Wed, 12 Mar 2014 17:39:06 +0000 (UTC) Delivered-To: ietf-ssh@NetBSD.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 8083A14A260 for ; Wed, 12 Mar 2014 17:39:02 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id 634FHM8mXoz7 for ; Wed, 12 Mar 2014 17:39:02 +0000 (UTC) Received: from che.mayfirst.org (che.mayfirst.org [209.234.253.108]) by mail.netbsd.org (Postfix) with ESMTP id D192614A259 for ; Wed, 12 Mar 2014 17:39:01 +0000 (UTC) Received: from [10.70.10.55] (unknown [38.109.115.130]) by che.mayfirst.org (Postfix) with ESMTPSA id 647BBF984; Wed, 12 Mar 2014 13:38:59 -0400 (EDT) Message-ID: <53209BB3.4000001@fifthhorseman.net> Date: Wed, 12 Mar 2014 13:38:59 -0400 From: Daniel Kahn Gillmor User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.2.0 MIME-Version: 1.0 To: Jeffrey Hutzelman , Peter Gutmann CC: "ietf-ssh@netbsd.org" , "" Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C737238A20F@uxcn10-6.UoA.auckland.ac.nz> <1394644793.23530.30.camel@destiny.pc.cs.cmu.edu> In-Reply-To: <1394644793.23530.30.camel@destiny.pc.cs.cmu.edu> X-Enigmail-Version: 1.6 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="tB43xxXnDwSsgsx4nGsPs65ujrApHuOAk" Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --tB43xxXnDwSsgsx4nGsPs65ujrApHuOAk Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 03/12/2014 01:19 PM, Jeffrey Hutzelman wrote: > The MODP groups given in RFC5114 are taken from DSS and NIST SP-800-56A= , > and do not have this same structure. The RFC has nothing to say on how= > they were selected, and my recollection from the last time I looked was= > that the NIST publications don't say anything either. It's not clear to me that there is any advantage in a DH key exchange to using the RFC 5114 discrete log groups. The selection of a discrete log group with a subgroup of targeted size q (instead of using a group with a safe prime modulus, which only allows subgroups of at worst (p-1)/2 if you exclude (p-1) as a valid public key) makes it costly to check whether the peer is forcing your shared secret into one of the other smaller subgroups. Note that this kind of subgroup-forcing attack was used in the DHE variant of Bhargavan et al's recent attack against client certification in TLS (other mistakes in the TLS protocol played a role in these attacks too, of course) Using a group with a known safe prime modulus should avoid this concern. --dkg --tB43xxXnDwSsgsx4nGsPs65ujrApHuOAk Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 Comment: Using GnuPG with Icedove - http://www.enigmail.net/ iQJ8BAEBCgBmBQJTIJuzXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRFQjk2OTEyODdBN0FEREUzNzU3RDkxMUVB NTI0MDFCMTFCRkRGQTVDAAoJEKUkAbEb/fpcjOcQALChFpJeivX2wF4odGMw5M9k DLIeDft4hUEa12tjGF0N0cWXtTk9cuhG9uwAQS1wmJJmMTpaELlX2kBan9L77tos 8YEKi/G7ZqU/0VwW5tGE6kV3J602Xojb5z1ZJFz+q4+PksG1PZDD6unCklHpmxQo XOW67JjekFFKNpL2W8WUHAHIAyBW/XVZaSN+MLc4S2h/SZNW8HCIuOA+GXO+hsdT OX4itYHvK9piWNwm2No41cgSnO47WfRiSms3gHcqDQ1I1jUEdwp41VvbH0+xD5u7 nbgwKKWed9NgRjdAE3jn6+uDDTOvKNIPR7/FNvlZW59cIMV//kSAfQpEfbgccKhB lp8EL8KAvh1yBWqQ++hJ7ORjGr31hn7My+d8utAp+G5WPPu78T3Q9V8ybnFS8hIb Nz4joyBcnbYHdJyWTpzJ0f0cMjiWHno7ob6p52OXLA+6eKVWGxK+OoivhDtmX+uI IQ39oR7GmRSBo3or0BBwdXJYxKyLKtw9Jgti4goBjZ/fSMVU8M/Eh8CkK0h7EiLN xl+SVfNvkRkqWyfEP95iFbvfGgUWm+KESBWClIM5U/7vFCwcDOcjEar8FX/Qg27K ryRJg+OQC/h89PCWeBzPbnXbj9od+Jy5wZcBOmlJ3f+FJnDNm7eK2CLGBZJt5YUr dd8aX2wcgK/dpu3sOnNJ =BW9w -----END PGP SIGNATURE----- --tB43xxXnDwSsgsx4nGsPs65ujrApHuOAk-- From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 11:42:17 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 113221A073F for ; Wed, 12 Mar 2014 11:42:17 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id qU0ZqoXiUeWX for ; Wed, 12 Mar 2014 11:42:16 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 37F461A0479 for ; Wed, 12 Mar 2014 11:42:16 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id E885714A26E; Wed, 12 Mar 2014 18:42:05 +0000 (UTC) Delivered-To: ietf-ssh@NetBSD.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id D327614A1C7 for ; Wed, 12 Mar 2014 18:42:03 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id xyETVyVQpV69 for ; Wed, 12 Mar 2014 18:42:03 +0000 (UTC) Received: from smtp02.srv.cs.cmu.edu (smtp02.srv.cs.cmu.edu [128.2.217.201]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id B387F14A1BF for ; Wed, 12 Mar 2014 18:42:02 +0000 (UTC) Received: from [192.168.202.157] (pool-108-39-221-65.pitbpa.fios.verizon.net [108.39.221.65]) (authenticated bits=0) by smtp02.srv.cs.cmu.edu (8.13.6/8.13.6) with ESMTP id s2CHJuMw017129 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Wed, 12 Mar 2014 13:19:59 -0400 (EDT) Message-ID: <1394644793.23530.30.camel@destiny.pc.cs.cmu.edu> Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] From: Jeffrey Hutzelman To: Peter Gutmann Cc: jhutz@cmu.edu, "" , "ietf-ssh@netbsd.org" Date: Wed, 12 Mar 2014 13:19:53 -0400 In-Reply-To: <9A043F3CF02CD34C8E74AC1594475C737238A20F@uxcn10-6.UoA.auckland.ac.nz> References: <9A043F3CF02CD34C8E74AC1594475C737238A20F@uxcn10-6.UoA.auckland.ac.nz> Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.8.4-0ubuntu1 Mime-Version: 1.0 Content-Transfer-Encoding: 7bit X-Scanned-By: mimedefang-cmuscs on 128.2.217.201 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On Wed, 2014-03-12 at 00:25 +0000, Peter Gutmann wrote: > This is from an early Oakley draft draft-ietf-ipsec-isakmp-oakley-03.txt that > references another Oakley draft draft-ietf-ipsec-oakley-01.txt which, however, > doesn't actually contain the text quoted above. So I guess the reference > would be [Citation needed ^ 2] or [Apocryphal ^ 2]. Actually, that text _does_ appear in RFC2412, in the introduction to appendix E, where the first five well-known groups are defined. The groups defined in RFC3526 have the same structure, but while that document does make reference to RFC2412, it does not actually claim the same method was used to select them. This should be relatively easy to verify, however. The MODP groups given in RFC5114 are taken from DSS and NIST SP-800-56A, and do not have this same structure. The RFC has nothing to say on how they were selected, and my recollection from the last time I looked was that the NIST publications don't say anything either. -- Jeff From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 12:29:39 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CCCEC1A078D for ; Wed, 12 Mar 2014 12:29:39 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.147 X-Spam-Level: X-Spam-Status: No, score=-2.147 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id dGHw798UOetI for ; Wed, 12 Mar 2014 12:29:37 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id DCA961A078A for ; Wed, 12 Mar 2014 12:29:37 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 0FF2C14A264; Wed, 12 Mar 2014 19:29:29 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 5031E14A262 for ; Wed, 12 Mar 2014 19:29:27 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id Hx-0hv_a32YM for ; Wed, 12 Mar 2014 19:29:26 +0000 (UTC) Received: from bacon.lysator.liu.se (vindbrygga.lysator.liu.se [IPv6:2001:6b0:17:f0a0::de]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 670F914A260 for ; Wed, 12 Mar 2014 19:29:25 +0000 (UTC) Received: from bacon.lysator.liu.se (localhost [127.0.0.1]) by bacon.lysator.liu.se (8.14.5+Sun/8.14.5) with ESMTP id s2CJTJsm009018; Wed, 12 Mar 2014 20:29:19 +0100 (MET) Received: (from nisse@localhost) by bacon.lysator.liu.se (8.14.5+Sun/8.14.5/Submit) id s2CJTItS009017; Wed, 12 Mar 2014 20:29:18 +0100 (MET) X-Authentication-Warning: bacon.lysator.liu.se: nisse set sender to nisse@lysator.liu.se using -f From: nisse@lysator.liu.se (Niels =?iso-8859-1?Q?M=F6ller?=) To: henrick@streamsec.se Cc: Watson Ladd , Daniel Kahn Gillmor , IETF TLS WG , ietf-ssh@netbsd.org Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> <531FB5DC.1010001@streamsec.se> <53202E8D.9090403@streamsec.se> Date: Wed, 12 Mar 2014 20:29:18 +0100 In-Reply-To: ("Niels =?iso-8859-1?Q?M=F6ller=22's?= message of "Wed, 12 Mar 2014 15:08:05 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (usg-unix-v) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list nisse@lysator.liu.se (Niels Möller) writes: > 1. This is a quick hack, not thoroughly tested or profiled, etc. And memory allocation was totally broken. I've put an updated version at http://www.lysator.liu.se/~nisse/misc/next-strong-prime.c Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 14:25:00 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 38CDF1A0784 for ; Wed, 12 Mar 2014 14:25:00 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.147 X-Spam-Level: X-Spam-Status: No, score=-2.147 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 1AKW3edUGc6g for ; Wed, 12 Mar 2014 14:24:57 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id C3B321A0781 for ; Wed, 12 Mar 2014 14:24:57 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id A3BF614A278; Wed, 12 Mar 2014 21:24:50 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 3443414A274 for ; Wed, 12 Mar 2014 21:24:48 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id zPkDxunYIsOH for ; Wed, 12 Mar 2014 21:24:47 +0000 (UTC) Received: from bacon.lysator.liu.se (vindbrygga.lysator.liu.se [IPv6:2001:6b0:17:f0a0::de]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 4362B14A23E for ; Wed, 12 Mar 2014 21:24:46 +0000 (UTC) Received: from bacon.lysator.liu.se (localhost [127.0.0.1]) by bacon.lysator.liu.se (8.14.5+Sun/8.14.5) with ESMTP id s2CLObAM012152; Wed, 12 Mar 2014 22:24:37 +0100 (MET) Received: (from nisse@localhost) by bacon.lysator.liu.se (8.14.5+Sun/8.14.5/Submit) id s2CLOZb7012151; Wed, 12 Mar 2014 22:24:35 +0100 (MET) X-Authentication-Warning: bacon.lysator.liu.se: nisse set sender to nisse@lysator.liu.se using -f From: nisse@lysator.liu.se (Niels =?iso-8859-1?Q?M=F6ller?=) To: henrick@streamsec.se Cc: Watson Ladd , Daniel Kahn Gillmor , IETF TLS WG , ietf-ssh@netbsd.org Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> <531FB5DC.1010001@streamsec.se> <53202E8D.9090403@streamsec.se> Date: Wed, 12 Mar 2014 22:24:35 +0100 In-Reply-To: ("Niels =?iso-8859-1?Q?M=F6ller=22's?= message of "Wed, 12 Mar 2014 15:08:05 +0100") Message-ID: User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/24.3 (usg-unix-v) MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: 8bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list nisse@lysator.liu.se (Niels Möller) writes: > 3. The 8192-bit prime definitely seems a bit expensive to generate. I've now ran the updated version of the program on a more high-end pc. For 8192 bits, it completed in about 52 minutes. Output: p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad33170d04507a33a85521abdf1cba64ecfb850458dbef0a8aea71575d060c7db3970f85a6e1e4c7abf5ae8cdb0933d71e8c94e04a25619dcee3d2261ad2ee6bf12ffa06d98a0864d87602733ec86a64521f2b18177b200cbbe117577a615d6c770988c0bad946e208e24fa074e5ab3143db5bfce0fd108e4b82d120a92108011a723c12a787e6d788719a10bdba5b2699c327186af4e23c1a946834b6150bda2583e9ca2ad44ce8dbbbc2db04de8ef92e8efc141fbecaa6287c59474e6bc05d99b2964fa090c3a2233ba186515be7ed1f612970cee2d7afb81bdd762170481cd0069127d5b05aa993b4ea988d8fddc186ffb7d! c90a6c08f4df435c93402849236c3fab4d27c7026c1d4dcb2602646dec9751e763dba37bdf8ff9406ad9e530ee5db382f413001aeb06a53ed9027d831179727b0865a8918da3edbebcf9b14ed44ce6cbaced4bb1bdb7f1447e6cc254b332051512bd7af426fb8f401378cd2bf5983ca01c64b92ecf032ea15d1721d03f482d7ce6e74fef6d55e702f46980c82b5a84031900b1c9e59e7c97fbec7e8f323a97a7e36cc88be0f1d45b7ff585ac54bd407b22b4154aacc8f6d7ebf48e1d814cc5ed20f8037e0a79715eef29be32806a1d58bb7c5da76f550aa3d8a1fbff0eb19ccb1a313d55cda56c9ec2ef29632387fe8d76e3c0468043e8f663f4860ee12bf2d5b0b7474d6e694f91e6dbe115974a3926f12fee5e438777cb6a932df8cd8bec4d073b931ba3bc832b68d9dd300741fa7bf8afc47ed2576f6936ba424663aab639c5ae4f5683423b4742bf1c978238f16cbe39d652de3fdb8befc848ad922222e04a4037c0713eb57a81a23f0c73473fc646cea306b4bcbc8862f8385ddfa9d4b7fa2c087e879683303ed5bdd3a062b3cf5b3a278a66d2a13f83f44f82ddf310ee074ab6a364597e899a0255dc164f31cc50846851df9ab48195ded7ea1b1d510bd7ee74d73faf36bc31ecfa268359046f4eb879f924009438b481c6cd7889a002ed5ee382bc9190da6fc026e47955! 8e4475677e9aa9e3050e2765694dfc81f56e880b96e7160c980dd98edd3dff! fffffffffffffff k = 4743157 elapsed time 3133.28s Which after a cursory look appears to agree with https://www.rfc-editor.org/rfc/rfc3526.txt (I guess the 47473157 vs 4743158 is an off-by-one error in my code. Does the spec's brackets in in "[2^8062 pi]" denote floor or round-to-nearest? Regards, /Niels -- Niels Möller. PGP-encrypted email is preferred. Keyid C0B98E26. Internet email is subject to wholesale government surveillance. From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 14:31:03 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 97ED11A074E for ; Wed, 12 Mar 2014 14:31:03 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.147 X-Spam-Level: X-Spam-Status: No, score=-2.147 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=ham Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nTIxZtHXF_Vx for ; Wed, 12 Mar 2014 14:31:00 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id E47DA1A073B for ; Wed, 12 Mar 2014 14:30:59 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id A4D2C14A22D; Wed, 12 Mar 2014 21:30:53 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 78A1F14A28A for ; Wed, 12 Mar 2014 21:30:45 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id nEfGeRaT7ES6 for ; Wed, 12 Mar 2014 21:30:44 +0000 (UTC) Received: from che.mayfirst.org (che.mayfirst.org [209.234.253.108]) by mail.netbsd.org (Postfix) with ESMTP id ACB3B14A1D2 for ; Wed, 12 Mar 2014 21:30:44 +0000 (UTC) Received: from [10.70.10.55] (unknown [38.109.115.130]) by che.mayfirst.org (Postfix) with ESMTPSA id 43280F986; Wed, 12 Mar 2014 17:30:41 -0400 (EDT) Message-ID: <5320D202.4070807@fifthhorseman.net> Date: Wed, 12 Mar 2014 17:30:42 -0400 From: Daniel Kahn Gillmor User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:24.0) Gecko/20100101 Icedove/24.2.0 MIME-Version: 1.0 To: =?UTF-8?B?TmllbHMgTcO2bGxlcg==?= , henrick@streamsec.se CC: Watson Ladd , IETF TLS WG , ietf-ssh@netbsd.org Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> <531FB5DC.1010001@streamsec.se> <53202E8D.9090403@streamsec.se> In-Reply-To: X-Enigmail-Version: 1.6 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="moJJCpL37U7aBEQ9BVXbUMPrrmlnvl3n4" Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list This is an OpenPGP/MIME signed message (RFC 4880 and 3156) --moJJCpL37U7aBEQ9BVXbUMPrrmlnvl3n4 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 03/12/2014 05:24 PM, Niels M=C3=B6ller wrote: > nisse@lysator.liu.se (Niels M=C3=B6ller) writes: >=20 >> 3. The 8192-bit prime definitely seems a bit expensive to generate. >=20 > I've now ran the updated version of the program on a more high-end pc. > For 8192 bits, it completed in about 52 minutes. Output: >=20 > p =3D 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc7= 4020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d= 6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5a= e9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd= 24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f17= 46c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c= 52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad331= 70d04507a33a85521abdf1cba64ecfb850458dbef0a8aea71575d060c7db3970f85a6e1e4= c7abf5ae8cdb0933d71e8c94e04a25619dcee3d2261ad2ee6bf12ffa06d98a0864d876027= 33ec86a64521f2b18177b200cbbe117577a615d6c770988c0bad946e208e24fa074e5ab31= 43db5bfce0fd108e4b82d120a92108011a723c12a787e6d788719a10bdba5b2699c327186= af4e23c1a946834b6150bda2583e9ca2ad44ce8dbbbc2db04de8ef92e8efc141fbecaa628= 7c59474e6bc05d99b2964fa090c3a2233ba186515be7ed1f612970cee2d7afb81bdd76217= 0481cd0069127d5b05aa993b4ea988d8fddc186ffb7d! > c90a6c08f4df435c93402849236c3fab4d27c7026c1d4dcb2602646dec9751e763dba3= 7bdf8ff9406ad9e530ee5db382f413001aeb06a53ed9027d831179727b0865a8918da3edb= ebcf9b14ed44ce6cbaced4bb1bdb7f1447e6cc254b332051512bd7af426fb8f401378cd2b= f5983ca01c64b92ecf032ea15d1721d03f482d7ce6e74fef6d55e702f46980c82b5a84031= 900b1c9e59e7c97fbec7e8f323a97a7e36cc88be0f1d45b7ff585ac54bd407b22b4154aac= c8f6d7ebf48e1d814cc5ed20f8037e0a79715eef29be32806a1d58bb7c5da76f550aa3d8a= 1fbff0eb19ccb1a313d55cda56c9ec2ef29632387fe8d76e3c0468043e8f663f4860ee12b= f2d5b0b7474d6e694f91e6dbe115974a3926f12fee5e438777cb6a932df8cd8bec4d073b9= 31ba3bc832b68d9dd300741fa7bf8afc47ed2576f6936ba424663aab639c5ae4f5683423b= 4742bf1c978238f16cbe39d652de3fdb8befc848ad922222e04a4037c0713eb57a81a23f0= c73473fc646cea306b4bcbc8862f8385ddfa9d4b7fa2c087e879683303ed5bdd3a062b3cf= 5b3a278a66d2a13f83f44f82ddf310ee074ab6a364597e899a0255dc164f31cc50846851d= f9ab48195ded7ea1b1d510bd7ee74d73faf36bc31ecfa268359046f4eb879f924009438b4= 81c6cd7889a002ed5ee382bc9190da6fc026e47955! > 8e4475677e9aa9e3050e2765694dfc81f56e880b96e7160c980dd98edd3dff! > fffffffffffffff > k =3D 4743157 > elapsed time 3133.28s >=20 > Which after a cursory look appears to agree with > https://www.rfc-editor.org/rfc/rfc3526.txt (I guess the 47473157 vs > 4743158 is an off-by-one error in my code. Does the spec's brackets in > in "[2^8062 pi]" denote floor or round-to-nearest? i was using floor for my calculations, not round-to-nearest. --dkg --moJJCpL37U7aBEQ9BVXbUMPrrmlnvl3n4 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1 Comment: Using GnuPG with Icedove - http://www.enigmail.net/ iQJ8BAEBCgBmBQJTINICXxSAAAAAAC4AKGlzc3Vlci1mcHJAbm90YXRpb25zLm9w ZW5wZ3AuZmlmdGhob3JzZW1hbi5uZXRFQjk2OTEyODdBN0FEREUzNzU3RDkxMUVB NTI0MDFCMTFCRkRGQTVDAAoJEKUkAbEb/fpcC18P/j+zYG/Nvs0nqD+W/2w/OAQL LY4T3BHbwpYLexhBfFkltpWuHI+nXVf0n3PZl7niJ90jWdxmFEjWh9TsDi8eMt1W FgWwUtH+gNz5MMINht78KKrFN2HnZ8IujE+NtAsUtZGQOGbI9yV6OCq0x09J2gpW 02UxrKpy7fOcY6gkpZPOJuN/5La9N3BGW7Za4TcpvbYthVqLKuDMoQsF0rvqqJu2 ZVZw9hNT57Gpgkf6dnaOai4ubZaPnVV8niNOsZeVXuLF6Jip3Tdy4i6GuENY6UM/ Q9GoLQlQuboZELFFYo5bLY3KdKQdWojzdJ4dKmXsloyheyhx6PJIj+Of3Vk+1yvL TJIAS3bP4zG0SmdcbyjYSpMk18SQxJtMJ1RJOwjCN6vj220js72RUcHpcJyzFfqX Z7CTqr/s9WfXUU1ri5CitkwE35RD7Z1L7cvck/rYbpGRDXkGOLE/5GedcGjrhKdd Mc814DbfJamrX/qPXhF4DTbJiXGt+Sh0+J6lXv2vR1fjGRrJ3lwGITZXP6M05ZTG nUfd32wvbsMra6mpwxn5NWBcOo6V2AHTkTGPNZqWXYgfxaocTIus4FbmQLEdkwrR ZxXhBZdO0YZuiwIi23gmKkMr/pJ5o7bkqGwbFK1lKkuJYshwdiFcczwShOMJFmWg 7ama2/ZySXddjeuLe3nE =SVTc -----END PGP SIGNATURE----- --moJJCpL37U7aBEQ9BVXbUMPrrmlnvl3n4-- From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 16:37:02 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id E05D91A07B1 for ; Wed, 12 Mar 2014 16:37:02 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.147 X-Spam-Level: X-Spam-Status: No, score=-2.147 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, MIME_8BIT_HEADER=0.3, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id B7Re6ndWE6KB for ; Wed, 12 Mar 2014 16:37:01 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 5D4311A02E6 for ; Wed, 12 Mar 2014 16:37:01 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id C1C8114A2A0; Wed, 12 Mar 2014 23:36:52 +0000 (UTC) Delivered-To: ietf-ssh@NetBSD.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 990F714A29F for ; Wed, 12 Mar 2014 23:36:49 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id HYCqS6FhsWmK for ; Wed, 12 Mar 2014 23:36:48 +0000 (UTC) Received: from smtp01.srv.cs.cmu.edu (smtp01.srv.cs.cmu.edu [128.2.217.200]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id A277C14A283 for ; Wed, 12 Mar 2014 23:36:47 +0000 (UTC) Received: from [128.2.193.239] (minbar.fac.cs.cmu.edu [128.2.193.239]) (authenticated bits=0) by smtp01.srv.cs.cmu.edu (8.13.6/8.13.6) with ESMTP id s2CLomlT012386 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Wed, 12 Mar 2014 17:50:49 -0400 (EDT) Message-ID: <1394661048.25748.40.camel@minbar.fac.cs.cmu.edu> Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] From: Jeffrey Hutzelman To: Niels =?ISO-8859-1?Q?M=F6ller?= Cc: jhutz@cmu.edu, henrick@streamsec.se, Watson Ladd , Daniel Kahn Gillmor , IETF TLS WG , ietf-ssh@NetBSD.org Date: Wed, 12 Mar 2014 17:50:48 -0400 In-Reply-To: References: <9A043F3CF02CD34C8E74AC1594475C7372387C9E@uxcn10-6.UoA.auckland.ac.nz> <201403072318.SAA28740@Chip.Rodents-Montreal.ORG> <20140308102142.GA25856@roeckx.be> <42833.1394302378@eng-mail01.juniper.net> <531F8ADF.3060002@fifthhorseman.net> <531FB5DC.1010001@streamsec.se> <53202E8D.9090403@streamsec.se> Content-Type: text/plain; charset="UTF-8" X-Mailer: Evolution 3.2.3-0ubuntu6 Content-Transfer-Encoding: 8bit Mime-Version: 1.0 X-Scanned-By: mimedefang-cmuscs on 128.2.217.200 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On Wed, 2014-03-12 at 22:24 +0100, Niels Möller wrote: > nisse@lysator.liu.se (Niels Möller) writes: > > > 3. The 8192-bit prime definitely seems a bit expensive to generate. > > I've now ran the updated version of the program on a more high-end pc. > For 8192 bits, it completed in about 52 minutes. Output: > > p = 0xffffffffffffffffc90fdaa22168c234c4c6628b80dc1cd129024e088a67cc74020bbea63b139b22514a08798e3404ddef9519b3cd3a431b302b0a6df25f14374fe1356d6d51c245e485b576625e7ec6f44c42e9a637ed6b0bff5cb6f406b7edee386bfb5a899fa5ae9f24117c4b1fe649286651ece45b3dc2007cb8a163bf0598da48361c55d39a69163fa8fd24cf5f83655d23dca3ad961c62f356208552bb9ed529077096966d670c354e4abc9804f1746c08ca18217c32905e462e36ce3be39e772c180e86039b2783a2ec07a28fb5c55df06f4c52c9de2bcbf6955817183995497cea956ae515d2261898fa051015728e5a8aaac42dad33170d04507a33a85521abdf1cba64ecfb850458dbef0a8aea71575d060c7db3970f85a6e1e4c7abf5ae8cdb0933d71e8c94e04a25619dcee3d2261ad2ee6bf12ffa06d98a0864d87602733ec86a64521f2b18177b200cbbe117577a615d6c770988c0bad946e208e24fa074e5ab3143db5bfce0fd108e4b82d120a92108011a723c12a787e6d788719a10bdba5b2699c327186af4e23c1a946834b6150bda2583e9ca2ad44ce8dbbbc2db04de8ef92e8efc141fbecaa6287c59474e6bc05d99b2964fa090c3a2233ba186515be7ed1f612970cee2d7afb81bdd762170481cd0069127d5b05aa993b4ea988d8fddc186ffb! 7d! > c90a6c08f4df435c93402849236c3fab4d27c7026c1d4dcb2602646dec9751e763dba37bdf8ff9406ad9e530ee5db382f413001aeb06a53ed9027d831179727b0865a8918da3edbebcf9b14ed44ce6cbaced4bb1bdb7f1447e6cc254b332051512bd7af426fb8f401378cd2bf5983ca01c64b92ecf032ea15d1721d03f482d7ce6e74fef6d55e702f46980c82b5a84031900b1c9e59e7c97fbec7e8f323a97a7e36cc88be0f1d45b7ff585ac54bd407b22b4154aacc8f6d7ebf48e1d814cc5ed20f8037e0a79715eef29be32806a1d58bb7c5da76f550aa3d8a1fbff0eb19ccb1a313d55cda56c9ec2ef29632387fe8d76e3c0468043e8f663f4860ee12bf2d5b0b7474d6e694f91e6dbe115974a3926f12fee5e438777cb6a932df8cd8bec4d073b931ba3bc832b68d9dd300741fa7bf8afc47ed2576f6936ba424663aab639c5ae4f5683423b4742bf1c978238f16cbe39d652de3fdb8befc848ad922222e04a4037c0713eb57a81a23f0c73473fc646cea306b4bcbc8862f8385ddfa9d4b7fa2c087e879683303ed5bdd3a062b3cf5b3a278a66d2a13f83f44f82ddf310ee074ab6a364597e899a0255dc164f31cc50846851df9ab48195ded7ea1b1d510bd7ee74d73faf36bc31ecfa268359046f4eb879f924009438b481c6cd7889a002ed5ee382bc9190da6fc026e479! 55! > 8e4475677e9aa9e3050e2765694dfc81f56e880b96e7160c980dd98edd3dff! > fffffffffffffff > k = 4743157 > elapsed time 3133.28s > > Which after a cursory look appears to agree with > https://www.rfc-editor.org/rfc/rfc3526.txt (I guess the 47473157 vs > 4743158 is an off-by-one error in my code. Does the spec's brackets in > in "[2^8062 pi]" denote floor or round-to-nearest? Neither 2412 nor 3526 says what they mean by that notation, but I'm assuming floor. However, in that case your result agrees with the spec. The value given in the spec is 2^8192 - 2^8128 - 1 + 2^64 * { [2^8062 pi] + 4743158 } This can be rewritten as: 2^8192 - 2^8128 + 2^64 * { [2^8062 pi] + 4743157 } + 2^64 - 1 The first two terms give the high-order 64 bits (all 1). The next term gives the middle bits, and agrees with your result. The last two terms give the low-order 64 bits. -- Jeff From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Wed Mar 12 21:50:52 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 92CDB1A08BC for ; Wed, 12 Mar 2014 21:50:52 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id foewQcQuUxl9 for ; Wed, 12 Mar 2014 21:50:51 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id BB1DA1A04F6 for ; Wed, 12 Mar 2014 21:50:51 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id ED63414A2C4; Thu, 13 Mar 2014 04:50:42 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 1C20814A2BF for ; Thu, 13 Mar 2014 04:50:39 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id JpsdGT0DIngX for ; Thu, 13 Mar 2014 04:50:38 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 1CAEA14A2B1 for ; Thu, 13 Mar 2014 04:50:34 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1394686238; x=1426222238; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=owoYs8ei3+NbfPwW2cvvTurR//k8a/Lpd7GKzYy6v4A=; b=LLcuNkBhAKilsQ7pCCN4zRtTS0cnG6FDSlapC94L8MARZb8tHxjRQby+ HXVMBOvNKVmlLxLEq/olqPl7Ubj4knpn+aU5j9nSg36sODTDTkv8ZpBAA iUTwXcVIWIt3U6QL7xPwxiBzjQuev4EOF0JMGAJlcOG9YHLOiP67b4U3I Y=; X-IronPort-AV: E=Sophos;i="4.97,644,1389697200"; d="scan'208";a="239369142" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.106 - Outgoing - Outgoing Received: from uxchange10-fe2.uoa.auckland.ac.nz ([130.216.4.106]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 13 Mar 2014 17:50:32 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe2.UoA.auckland.ac.nz ([130.216.4.106]) with mapi id 14.03.0174.001; Thu, 13 Mar 2014 17:50:32 +1300 From: Peter Gutmann To: "ietf-ssh@netbsd.org" , "" Subject: Re: [TLS] Still missing: TLS_ECDH_anon_WITH_AES_xxx_GCM_SHAxxx Thread-Topic: [TLS] Still missing: TLS_ECDH_anon_WITH_AES_xxx_GCM_SHAxxx Thread-Index: Ac8+d8OhohuCIUnlQ2Op/mVzyohdOQ== Date: Thu, 13 Mar 2014 04:50:32 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C737238AD92@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Daniel Kahn Gillmor writes:=0A= =0A= >0) either the software or the admin must manually provision the certificat= e=0A= >for the server; this means making decisions about questions that don't=0A= >necessarily have any good answers, which is not a situation you want your= =0A= >users to be in. Servers operating in a pool now need to have some sort of= =0A= >secret key distribution mechanism, for example.=0A= =0A= One option for this is for the server to auto-generate the cert on first=0A= install/setup. The alternative that's currently used on way too many devic= es=0A= is for them to have a pre-generated generic cert with incorrect ID informat= ion=0A= with the private key shared across all devices.=0A= =0A= Peter.= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Thu Mar 13 01:06:09 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 250B61A0960 for ; Thu, 13 Mar 2014 01:06:09 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id eDOR-ROsjKEA for ; Thu, 13 Mar 2014 01:06:08 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 12F541A094F for ; Thu, 13 Mar 2014 01:06:08 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 96E4014A2C5; Thu, 13 Mar 2014 08:05:54 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: by mail.netbsd.org (Postfix, from userid 1347) id 39B7714A2B1; Thu, 13 Mar 2014 08:05:54 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 5D72914A27E for ; Wed, 12 Mar 2014 22:09:03 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id c2BV5H2yyu3l for ; Wed, 12 Mar 2014 22:09:02 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 2859414A272 for ; Wed, 12 Mar 2014 22:08:58 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1394662142; x=1426198142; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=cmqnyQ4ZtW8BPXaJH5P01+cfQjFYjtLg5F6J9yEKYZc=; b=j/DIHcdrrDPjAt+bx/Bv8ANQtDdEeY3/fZs7CcRVSDhJNpwnJE7G6akR KVwHnnBbnADbAuM3Z2VGBZTciBTDDETpT8XDTZruuKBh8z5hgzBC8bqG8 Su3qxiYmr5PS17+CsaAUUKRxhzX5Mq6CuL6s9kXaCfnQAAOJQyeMC9rUs 8=; X-IronPort-AV: E=Sophos;i="4.97,641,1389697200"; d="scan'208";a="239227251" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.125 - Outgoing - Outgoing Received: from uxchange10-fe3.uoa.auckland.ac.nz ([130.216.4.125]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 13 Mar 2014 11:08:56 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe3.UoA.auckland.ac.nz ([130.216.4.125]) with mapi id 14.03.0174.001; Thu, 13 Mar 2014 11:08:56 +1300 From: Peter Gutmann To: "" , "ietf-ssh@netbsd.org" Subject: Re: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] Thread-Topic: [TLS] MODP group modulus derivation [was: Re: I can has SHA-1 hashes for RFC 2409/3526 MODP groups?] Thread-Index: Ac8+P6khvKF7r+7sSbqbCVajK6GYkw== Date: Wed, 12 Mar 2014 22:08:55 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C737238AAAF@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Daniel Kahn Gillmor writes:=0A= =0A= >It's not clear to me that there is any advantage in a DH key exchange to= =0A= >using the RFC 5114 discrete log groups.=0A= =0A= There's actually an enormous disadvantage to using those groups, the RFC 35= 26=0A= and earlier MODP groups set the generator to 2, which is quite efficient to= =0A= work with. RFC 5114 uses a generator of the same size as the prime, which = is=0A= stunningly inefficient (I've referred to the 5114 groups as the "WTF groups= "=0A= in code in the past). I have no idea why the RFC would choose such an awfu= l=0A= generator...=0A= =0A= Peter.=0A= =0A= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Thu Mar 13 07:38:15 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 2524D1A09D8 for ; Thu, 13 Mar 2014 07:38:15 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 5vvIsJRRz7B6 for ; Thu, 13 Mar 2014 07:38:14 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 032AB1A09C9 for ; Thu, 13 Mar 2014 07:38:14 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 9016014A251; Thu, 13 Mar 2014 14:38:06 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id ED6D514A1BD for ; Thu, 13 Mar 2014 14:38:03 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id 4jgiYzDEwTjq for ; Thu, 13 Mar 2014 14:38:03 +0000 (UTC) Received: from entima.net (entima.net [78.129.143.175]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 2A27D14A1AC for ; Thu, 13 Mar 2014 14:38:02 +0000 (UTC) Received: from [10.93.112.86] (94.197.120.97.threembb.co.uk [94.197.120.97]) by entima.net (Postfix) with ESMTPSA id 7820A601CC; Thu, 13 Mar 2014 13:22:19 +0000 (GMT) User-Agent: K-9 Mail for Android In-Reply-To: <9A043F3CF02CD34C8E74AC1594475C737238AD92@uxcn10-6.UoA.auckland.ac.nz> References: <9A043F3CF02CD34C8E74AC1594475C737238AD92@uxcn10-6.UoA.auckland.ac.nz> MIME-Version: 1.0 Content-Transfer-Encoding: 8bit Content-Type: text/plain; charset=UTF-8 Subject: Re: [TLS] Still missing: TLS_ECDH_anon_WITH_AES_xxx_GCM_SHAxxx From: Alyssa Rowan Date: Thu, 13 Mar 2014 13:22:14 +0000 To: Peter Gutmann ,"ietf-ssh@netbsd.org" ,"" Message-ID: <826e1c57-6d87-47e7-a064-347992fd5606@email.android.com> Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA512 On 13 March 2014 04:50:32 GMT+00:00, Peter Gutmann wrote: >The alternative that's currently used on way too many >devices >is for them to have a pre-generated generic cert with incorrect ID >information >with the private key shared across all devices. Can we perhaps make that a SHOULD NOT (or even a MUST NOT), if it somehow isn't already? It's way too common in the wild, and it really is next to useless practice from the same kind of wilful carelessness that brought the world so many default/engineering/field service passwords/backdoors. The related, but more unwitting, case of devices (often embedded) with bad RNGs which don't collect enough entropy on warmup generating keys on startup which turn out to be one of a globally limited set of practically-enumerable keys is also one for implementers and testers to watch out for, and is also actively seen and exploited in the wild: I think we should have strong advice about that as it's a depressingly common pitfall. - -- /akr -----BEGIN PGP SIGNATURE----- Version: APG v1.0.9 iQI3BAEBCgAhBQJTIbEGGhxBbHlzc2EgUm93YW4gPGFrckBha3IuaW8+AAoJEOyE jtkWi2t6QosP/i0xem6cxWoaPbO0OWmsKa05Y9VudKvl8nBW8+xLxNo6SPq1rLaI +y+A/PpYHWBDKUoQHp0KRr23mAcjq175zYSKE4DBciRSjmZ/HGgedoElKYcvF8mr erB8ruUKqdeFn5Y0niUTdyu7I0btxsjnGEkiqjxUp3Nvj+6Z66dQ45hNU86QUP5h P8TgHfY1KlOU20FnVnHgiZD97upaBG9uWTwVYnw6mQFu/AEXwASR6U0BT0VrF+j6 wHKPxZhKHa5IhPwRIka0CDXGKLFdxDdF0uLUQ6leEazznWx164itBRwWJOKr3FB4 xQEqtMVJeQen+nAYQwA4qHsKoG/p+s13SKCWcYiLd6FDzasRY215b0ArtmrDi5Kh nPu6WeZaadi6bLw31b8KXChennTYe+B+1mLatjAyFVeQ5hZI3dcXkZlX1gB35KrO Q6zIsoVRQqovmyfuhIOg7XDUc7FENWyCyCRBEPNI7Vzyw24oMNA6lmBBodbAPg9Q 9IqiVEjXdvreWT6f7ppy5Ns3F+2Vb/RLPhyl79u3NgfRIDQVZYz7DTqLmsTADubs LJop+2iVMDUD6o+14GKqmYgw/Sf/t2uWBsiIEib2LPZ5ebeso0BldcsCmTt0Fbja CmPGgWgKIjfQzJlA9ijq5rC0+xji9iYDg2d1+uSGdRX2RbPr0qmgmUcP =/9kY -----END PGP SIGNATURE----- From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Fri Mar 14 00:48:19 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id CB63D1A008F for ; Fri, 14 Mar 2014 00:48:19 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: -2.447 X-Spam-Level: X-Spam-Status: No, score=-2.447 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RP_MATCHES_RCVD=-0.547] autolearn=unavailable Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id zyCKBFxkYgxM for ; Fri, 14 Mar 2014 00:48:17 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 157B11A0090 for ; Fri, 14 Mar 2014 00:48:17 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 6BC6B14A23A; Fri, 14 Mar 2014 07:48:08 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: by mail.netbsd.org (Postfix, from userid 1347) id 0F90314A1D2; Fri, 14 Mar 2014 07:48:08 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 0D4F914A3E8 for ; Thu, 13 Mar 2014 23:01:34 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Authentication-Results: mail.NetBSD.org (amavisd-new); dkim=pass (1024-bit key) header.d=auckland.ac.nz Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id cQTBxjx1vk4E for ; Thu, 13 Mar 2014 23:01:33 +0000 (UTC) Received: from mx2.auckland.ac.nz (mx2.auckland.ac.nz [130.216.125.245]) (using TLSv1 with cipher DHE-RSA-CAMELLIA256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id D814C14A1FC for ; Thu, 13 Mar 2014 23:01:29 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=simple/simple; d=auckland.ac.nz; i=@auckland.ac.nz; q=dns/txt; s=uoa; t=1394751693; x=1426287693; h=from:to:subject:date:message-id: content-transfer-encoding:mime-version; bh=tN2DgIxmOMliBssg+KS1fOtSl++vO7+G+UXOPJJi5HQ=; b=cA6h0WyzjUzK9QwtZSLhjRAqJcZQV/waSmato8whkWXWEhOiJ6/XkUAC pDMmGyy6xOOckG5LRRL6YgBkLAjkxAknVybzP0NbOQYUJzk6hr5Hq8Ms2 t9PfhZUlomLsNPldEoYwExPvikMTBw1xlg7jIN2BlVB5Tj0IQr+40FcPb c=; X-IronPort-AV: E=Sophos;i="4.97,649,1389697200"; d="scan'208";a="239570070" X-Ironport-HAT: MAIL-SERVERS - $RELAYED X-Ironport-Source: 130.216.4.112 - Outgoing - Outgoing Received: from uxchange10-fe1.uoa.auckland.ac.nz ([130.216.4.112]) by mx2-int.auckland.ac.nz with ESMTP/TLS/AES128-SHA; 14 Mar 2014 12:01:27 +1300 Received: from UXCN10-6.UoA.auckland.ac.nz ([169.254.10.53]) by uxchange10-fe1.UoA.auckland.ac.nz ([130.216.4.112]) with mapi id 14.03.0174.001; Fri, 14 Mar 2014 12:01:26 +1300 From: Peter Gutmann To: "" , "ietf-ssh@netbsd.org" Subject: Re: [TLS] Still missing: TLS_ECDH_anon_WITH_AES_xxx_GCM_SHAxxx Thread-Topic: [TLS] Still missing: TLS_ECDH_anon_WITH_AES_xxx_GCM_SHAxxx Thread-Index: Ac8/ECkmgTZ4h3K+S8u8HHUPIcV3Hw== Date: Thu, 13 Mar 2014 23:01:26 +0000 Message-ID: <9A043F3CF02CD34C8E74AC1594475C737238B6C3@uxcn10-6.UoA.auckland.ac.nz> Accept-Language: en-NZ, en-GB, en-US Content-Language: en-NZ X-MS-Has-Attach: X-MS-TNEF-Correlator: x-originating-ip: [130.216.158.4] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list Alyssa Rowan writes:=0A= =0A= >Can we perhaps make that a SHOULD NOT (or even a MUST NOT), if it somehow= =0A= >isn't already? It's way too common in the wild, and it really is next to= =0A= >useless practice from the same kind of wilful carelessness that brought th= e=0A= >world so many default/engineering/field service passwords/backdoors.=0A= =0A= I doubt it'll make any difference, those who would read and follow the RFC = on=0A= this point won't be using insecure certs/keys anyway, and those who are usi= ng=0A= them will ignore (or not even read to that point) the RFC. I've heard this= =0A= sort of thing referred to in the past as "workgroup posturing", and that's= =0A= unfortunately what it'll be...=0A= =0A= Peter.=0A= From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Thu Mar 27 21:02:54 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 544F21A07D5 for ; Thu, 27 Mar 2014 21:02:54 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 4.407 X-Spam-Level: **** X-Spam-Status: No, score=4.407 tagged_above=-999 required=5 tests=[BAYES_80=2, MIME_8BIT_HEADER=0.3, RCVD_IN_BL_SPAMCOP_NET=1.347, RCVD_IN_SORBS_WEB=0.77, T_RP_MATCHES_RCVD=-0.01] autolearn=no Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id pQcU1zvhrQrR for ; Thu, 27 Mar 2014 21:02:52 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id C66281A07C8 for ; Thu, 27 Mar 2014 21:02:52 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id 0C5EF14A34B; Fri, 28 Mar 2014 04:02:48 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id 4A98E14A2FD for ; Fri, 28 Mar 2014 04:02:47 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id Df-M1OdoNp8T for ; Fri, 28 Mar 2014 04:02:46 +0000 (UTC) Received: from mail.kz (frontend03n.mail.kz [92.46.53.18]) by mail.netbsd.org (Postfix) with ESMTP id 5A11914A2CE for ; Fri, 28 Mar 2014 04:02:46 +0000 (UTC) Received: from [221.161.197.36] (account astana_@mail.kz HELO mail.kz) by frontend03n.mail.kz (CommuniGate Pro SMTP 5.2.13) with ESMTPA id 338914638 for ietf-ssh@netbsd.org; Fri, 28 Mar 2014 10:02:11 +0600 Date: Fri, 28 Mar 2014 13:02:24 +0900 From: "=?windows-1251?Q?=C3=E0=EB=FE=F8=E0_=D3=EB=FC=FF=F8=E8=ED=E0?=" Organization: belqgjnldcfna X-Priority: 3 (Normal) Message-ID: <120979064.20140328130224@mail.kz> To: ietf-ssh@netbsd.org Subject: =?windows-1251?Q?=CD=E0=F3=EA=E0=2C=2C=EF=F0=E8=E1=FB=EB=FC=ED=EE=E3=EE=3A=E1=E8=E7=ED=E5=F1=F1=E0?= MIME-Version: 1.0 Content-Type: text/plain; charset=windows-1251 Content-Transfer-Encoding: 8bit Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list http://coolcuts.cioannides.com/hjzh/r1.php From bounces-ietf-ssh-owner-secsh-tyoxbijeg7-archive=lists.ietf.org@NetBSD.org Sun Mar 30 11:07:49 2014 Return-Path: X-Original-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Delivered-To: ietfarch-secsh-tyoxbijeg7-archive@ietfa.amsl.com Received: from localhost (ietfa.amsl.com [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 72AA41A08BC for ; Sun, 30 Mar 2014 11:07:49 -0700 (PDT) X-Virus-Scanned: amavisd-new at amsl.com X-Spam-Flag: NO X-Spam-Score: 4.636 X-Spam-Level: **** X-Spam-Status: No, score=4.636 tagged_above=-999 required=5 tests=[BAYES_50=0.8, RCVD_IN_BL_SPAMCOP_NET=1.347, SORTED_RECIPS=2.499, T_RP_MATCHES_RCVD=-0.01] autolearn=no Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id OGlTjoeVwx0J for ; Sun, 30 Mar 2014 11:07:46 -0700 (PDT) Received: from mail.netbsd.org (mail.NetBSD.org [IPv6:2001:4f8:3:7::25]) by ietfa.amsl.com (Postfix) with ESMTP id 73C671A08B9 for ; Sun, 30 Mar 2014 11:07:46 -0700 (PDT) Received: by mail.netbsd.org (Postfix, from userid 605) id D200014A400; Sun, 30 Mar 2014 18:07:39 +0000 (UTC) Delivered-To: ietf-ssh@netbsd.org Received: from localhost (localhost [127.0.0.1]) by mail.netbsd.org (Postfix) with ESMTP id D0C8314A357; Sun, 30 Mar 2014 18:07:37 +0000 (UTC) X-Virus-Scanned: amavisd-new at NetBSD.org Received: from mail.netbsd.org ([127.0.0.1]) by localhost (mail.NetBSD.org [127.0.0.1]) (amavisd-new, port 10025) with ESMTP id z4JdRWc_KMSK; Sun, 30 Mar 2014 18:07:37 +0000 (UTC) Received: from mail.psvs.cz (mail.psvs.cz [80.188.2.198]) (using TLSv1 with cipher DHE-RSA-AES256-SHA (256/256 bits)) (No client certificate requested) by mail.netbsd.org (Postfix) with ESMTPS id 8062114A427; Sun, 30 Mar 2014 18:07:16 +0000 (UTC) Received: from psvs.cz (77-52-192-166.dialup.umc.net.ua [77.52.192.166]) (authenticated bits=0) by mail.psvs.cz (8.14.3/8.14.3/Debian-5+lenny1) with ESMTP id s2UEE4QN013047; Sun, 30 Mar 2014 16:14:07 +0200 Message-ID: <7FE47C4B.3B9080A9@psvs.cz> Date: Sun, 30 Mar 2014 16:14:15 +0200 From: "Guillain" User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; de; rv:1.8.1.12) Gecko/20080213 Thunderbird/2.0.0.12 MIME-Version: 1.0 To: , , , , , , , , , , , , , , , , , , , , , , , , Subject: Brand name watches at the clearance prices Content-Type: text/plain; charset="iso-8859-1" Content-Transfer-Encoding: 7bit X-Greylist: Sender succeeded SMTP AUTH authentication, not delayed by milter-greylist-3.0 (mail.psvs.cz [80.188.2.198]); Sun, 30 Mar 2014 16:14:16 +0200 (CEST) X-Virus-Scanned: clamav-milter 0.97.3 at mail X-Virus-Status: Clean Sender: ietf-ssh-owner@NetBSD.org List-Id: ietf-ssh.NetBSD.org Precedence: list On time delivery on your internet timepiece purchases http://byflowers.by/nsprrnb.php