[Cfrg] Password - proof 36bit/round

Otto Ersek <oersek@gmail.com> Wed, 02 November 2016 05:51 UTC

Return-Path: <oersek@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id E90D612999F for <cfrg@ietfa.amsl.com>; Tue, 1 Nov 2016 22:51:49 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.7
X-Spam-Status: No, score=-2.7 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, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id UrtxmXHhx-wB for <cfrg@ietfa.amsl.com>; Tue, 1 Nov 2016 22:51:48 -0700 (PDT)
Received: from mail-wm0-x234.google.com (mail-wm0-x234.google.com [IPv6:2a00:1450:400c:c09::234]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id E1B3C1294BD for <cfrg@irtf.org>; Tue, 1 Nov 2016 22:51:47 -0700 (PDT)
Received: by mail-wm0-x234.google.com with SMTP id t79so14132067wmt.0 for <cfrg@irtf.org>; Tue, 01 Nov 2016 22:51:47 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:subject:message-id:date:user-agent:mime-version :content-transfer-encoding; bh=g4O/8SyfY5cyp/VQtn+4Zhs4HHg7l+Ty/SrMtg0w/yo=; b=IaLUcru0WzMFfHxvZbNDNwk7hmAAaAxgso0q8envLSmcFFd25ThliSAzLGZTL2Z0qT yjycJUUIYqwjL44kvJiyl7fnf/c8eNn0x+aToNcR0/C9Iby0tkr1geerOl5UARl7+Xsv 4tfOjIR/Bo0ZEQDb7z/jLq6nSYshR25NzXTAX2S27DGJ8HicCd5Lj9ZtkonWF6XDziS2 ehZjf5mqPg+l9GPcjyEUCqQsl7d9B9tlYDpaPTPLLi+jpWQTLckYnncKNpbxVWtSx7+k 13RoZWff6TOTVBFQ+to6yPkIOujStZeH13tB2mJR/iuF+2zNusO7IONE8Y+SSeJycsUR 5SPg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:subject:message-id:date:user-agent :mime-version:content-transfer-encoding; bh=g4O/8SyfY5cyp/VQtn+4Zhs4HHg7l+Ty/SrMtg0w/yo=; b=EBoJSj4rNAtBlNl9DcD37dcu2TBeYen6cYt16h2/Bh06GQUhfiG2dID1+5UbEv5rqb zDZiS7ovo0lf5ID3IyiDVo28UjiXu3DBVFYCzsOjrUKOv7k8mXxJUIglJsz4HPiCUXC7 9b4dR5BLlB99HTAXO7bDFEXC4S+VRiYcaTKRRA/vgTv+vs0HfhyxS2QaEFeCduRt88WO prgGhbCeQENlN1CAq1ZkCdt61cUxGDf3phGgLfEtTe7BQdltc0a1CHipgiyf9Af52ZUE nTzyMPq+UiBAQ0w9cucGI3aSatGhVo/J/FSyYul7PR6/1Amcq2sXQ0gUlT/dP0Asdq5Y vSkQ==
X-Gm-Message-State: ABUngvduoTchpXUeUK4RU83RH7BIEz1BAzJHtd+x63kj054GaeCA+wp472oau9tHGsSXhQ==
X-Received: by with SMTP id w64mr1470841wmf.13.1478065906292; Tue, 01 Nov 2016 22:51:46 -0700 (PDT)
Received: from [] ( []) by smtp.gmail.com with ESMTPSA id jb2sm528881wjb.44.2016. for <cfrg@irtf.org> (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Tue, 01 Nov 2016 22:51:45 -0700 (PDT)
From: Otto Ersek <oersek@gmail.com>
To: cfrg@irtf.org
Message-ID: <d2ead58f-8616-f0b6-466f-1be8a8bd95c7@gmail.com>
Date: Wed, 02 Nov 2016 06:51:44 +0100
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:45.0) Gecko/20100101 Thunderbird/45.3.0
MIME-Version: 1.0
Content-Type: text/plain; charset="utf-8"; format="flowed"
Content-Transfer-Encoding: 8bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/J4I7GrVZ2wXzmYVeQZw9264GVCc>
Subject: [Cfrg] Password - proof 36bit/round
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
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: Wed, 02 Nov 2016 05:51:50 -0000

I was asked to give a proof for the 36bits

Let us additionally implement a key-logger (a honest one this time) that 
keeps track of user input and appends to the modified text the hashed 
value of committed changes before final hashing.

I didn’t want to mention the key-logger in the original post because the 
ideas presented there were already difficult to digest. But let us use 
the tools that threaten passwords to make this stronger.

Given a text of n characters (including spaces) one has n*(n+1)/2 
possibilities to select a consecutive sub-text (proof by induction)
But one has (since the key-logger is active) 2*n + 1 ways to paste the 
text back.
This gives a total of P = n*(n+1)* (2*n + 1)/2 possibilities °)
if n = 2^10 as requested then P > 2^30 thus in bits 30, additionally we 
pre/append a char from base64 that one accounts for the remaining 6

°) One could even eliminate the divisor: if the end of a selection 
selection is BEFORE the start then let’s paste in the clipboard the 
wrapped around text → another bit would be gained!

Bonus: For the next round these values increase since n increases by the 
count of the pasted chars.

Thus we have a simple drag & drop = copy & paste authentication
I this correct?