Re: [CFRG] Using Diffie-Hellman With a Non-prime Modulus

Michael D'Errico <mike-list@pobox.com> Fri, 30 October 2020 02:28 UTC

Return-Path: <mike-list@pobox.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id EB4A93A0147 for <cfrg@ietfa.amsl.com>; Thu, 29 Oct 2020 19:28:54 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.345
X-Spam-Level:
X-Spam-Status: No, score=-2.345 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, NICE_REPLY_A=-0.247, RCVD_IN_DNSWL_BLOCKED=0.001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=pobox.com; domainkeys=pass (1024-bit key) header.from=mike-list@pobox.com header.d=pobox.com
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 a4vW69ZSM0wm for <cfrg@ietfa.amsl.com>; Thu, 29 Oct 2020 19:28:53 -0700 (PDT)
Received: from pb-smtp21.pobox.com (pb-smtp21.pobox.com [173.228.157.53]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id B0EA63A0114 for <cfrg@irtf.org>; Thu, 29 Oct 2020 19:28:53 -0700 (PDT)
Received: from pb-smtp21.pobox.com (unknown [127.0.0.1]) by pb-smtp21.pobox.com (Postfix) with ESMTP id EE75F105927 for <cfrg@irtf.org>; Thu, 29 Oct 2020 22:28:50 -0400 (EDT) (envelope-from mike-list@pobox.com)
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=pobox.com; h=subject:to :references:from:message-id:date:mime-version:in-reply-to :content-type:content-transfer-encoding; s=sasl; bh=qH1xOLDShrrT V93D6yeU9u8AC7Q=; b=RluTleWOKXDe9Z/yhzC0FJa67QmvMCqOdSC/HZkTSUED KzSNYsVh1zSN8SELK6SfLinGvVg6negzeG0YbYa743yyYgEALt7IcBSnBsRP1D3x vLxJoqAs1R6M8XRSzjFgOPWXwgGNbR0/ZWfNUzBqleIZYRn5rf3Fft8ljbOmFbY=
DomainKey-Signature: a=rsa-sha1; c=nofws; d=pobox.com; h=subject:to :references:from:message-id:date:mime-version:in-reply-to :content-type:content-transfer-encoding; q=dns; s=sasl; b=lmYefR hxSHf59xhXEq39Dti04JXWeYKGuu0IeId/4xAbhn56KeG7QVsYlisz+BYugLTJQu GnTkyRz6iBRq1wmhTCKKXqbfIgSIhMnMb5ZCFiAtuU2iLGcqJqkgsZIPD3NYG40O LG1UQ/q8tKpbwnA+jiUJYmvlelaKXDlKIqD4Y=
Received: from pb-smtp21.sea.icgroup.com (unknown [127.0.0.1]) by pb-smtp21.pobox.com (Postfix) with ESMTP id E86DF105926 for <cfrg@irtf.org>; Thu, 29 Oct 2020 22:28:50 -0400 (EDT) (envelope-from mike-list@pobox.com)
Received: from MacBookPro.local (unknown [72.227.128.99]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by pb-smtp21.pobox.com (Postfix) with ESMTPSA id EDE1A105925 for <cfrg@irtf.org>; Thu, 29 Oct 2020 22:28:47 -0400 (EDT) (envelope-from mike-list@pobox.com)
To: cfrg@irtf.org
References: <6f5bddd5-04c8-45bf-87b1-7bb1e852666f@www.fastmail.com> <817BB671-266A-41F1-89E8-4BB740B61B93@shiftleft.org> <7b0d0e0c-bb1d-46e3-b513-2a9327d21bd2@www.fastmail.com> <BN7PR11MB2641B00395B31AA668B8CB7EC1140@BN7PR11MB2641.namprd11.prod.outlook.com>
From: Michael D'Errico <mike-list@pobox.com>
Message-ID: <64e739d3-24c6-7b58-affe-b1e787fb8bee@pobox.com>
Date: Thu, 29 Oct 2020 22:28:46 -0400
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.13; rv:68.0) Gecko/20100101 Thunderbird/68.12.1
MIME-Version: 1.0
In-Reply-To: <BN7PR11MB2641B00395B31AA668B8CB7EC1140@BN7PR11MB2641.namprd11.prod.outlook.com>
Content-Type: text/plain; charset=utf-8; format=flowed
Content-Language: en-US
X-Pobox-Relay-ID: A3FE93FC-1A57-11EB-BA37-D609E328BF65-38729857!pb-smtp21.pobox.com
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/3PR8t4L4Xx6yYYFmdZW0rvj--Lc>
Subject: Re: [CFRG] Using Diffie-Hellman With a Non-prime Modulus
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Fri, 30 Oct 2020 02:28:55 -0000

> It's not true in general that exponentiation modulo M is cyclic with period M-1.  It is true if M is prime; however you are considering composite M, hence Fermat does not apply.

My point exactly.  All the current published groups
have a prime modulus M, which might be problematic
due to Fermat.  This leads me to consider non-prime
moduli as a possible improvement.

> Mike Hamburg already outlined the issues for M with public factorization. For M with a secret factorization, there are a number of ways for us to hide a backdoor in the DH operation, for example, https://eprint.iacr.org/2016/644.pdf (not the best, IMHO, just the first reference I found) - hence, good luck in getting anyone to trust that you didn't...

I'm not doing anything in secret.  It's all here on
this mailing list.  Sure, one part of the threat
model of the Internet is that the standards writers
are sabotaging the very standards we're relying on.
I've no doubt that this has occurred and is occurring
now.  If I can't figure out a way to objectively show
that my results are better than the current groups
then I won't pursue it further.  I've no stake in
this other than trying to make the Internet better.

Thank you for providing a reference.

Mike