Internet Public Service Abuse Mitigation with a Time Ticket Sub-Protocol

(technical note)

Thierry Moreau

Document Number C005403


Copyright (C) 2012 CONNOTECH Experts-conseils inc.

Verbatim redistribution of the present document is authorized.

This document 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.

Specifications subject to change without notice.

Document Revision History






Current version



Initial release

Table of contents

1. Preface

2. Problem Statement

3. Network Arrangement

4. Key Sizes Matching Short Key Life Expectancy

5. Operating Principles

1. Preface

The present technical note discloses a portion of a detailed design for a larger project under development. The contents of the disclosure is a small portion of the overall technology being integrated, fulfilling a very adhoc purpose.

The purpose of the disclosure is to put the novel aspects in the public domain (to the extent they are not patented by others) and to benefit from some feedback, either from a review of the disclosure itself or implementation experience in case anyone finds the ideas useful.

2. Problem Statement

An application server is available on the public Internet, without any client authentication mechanism. It could be qualified as an anonymous service, but it more precisely serves users wishing to enroll in an authentcation scheme, so the legitimate users should not remain anonymous for a long time. The legitimate usage of the service is under direct supervision by an end-user, infrequently. The low usage nfrequency makes it practical to insert an artificial latency in the service provision if it can help. Roughly, the delay could be as long as 3 seconds, maybe stretching to 12 seconds as a worst case.

The problem with the service is a possible diversion of its purpose, because it provides a functionality in the early steps, benefiting to the client before the application logic is able detect the diversion and cancel the service provision instance. A similar situation occurs when an adversary attempts an on-line dictionary attack on a password-based authentication scheme, but the classical solution is to block the user account after a small number of failed attempts (not applicable for an anonymous service). A similar situation occurs, at least in theory, if the early service response may assist an adversary in the cryptanalysis of a cryptographic primitive. The most likely incident in this respect would be the attacker learning multiple random challenge values with aborted challenge-response authentication cycles hoping to cryptanalyse the server PRNG internal state. The classical solution is to use cryptographically strong PRNGs where it matters.

Also part of the problem statement is a preference with a stable application server environment, because IT security mechanisms are less vulnerable to insider fraud when fewer programmers and system operators need access to it.

Classical denial-of-service mitigation is not strictly part of the problem statement.

3. Network Arrangement

The time ticker server provides UDP services for the time ticket sub-protocol and the application server would typically provides its services using TCP. A direct link is available between the two, with privacy and integrity protection.

The client systems must complete a time ticket protocol exchange before attempting to connect to the application server. The time ticket value obtained in this exchange (notation <x1,resp> below) serves as a one-time password presented to the application server.

4. Key Sizes Matching Short Key Life Expectancy

The time ticket sub-protocol uses a short life expectancy public-private key pair for an integer factorisation family public key primitive. Specifically, we use the BBS cryptographically strong PRNG construction which has the same trapdoor as the Rabin-Williams cryptosystem. The public key function is xi+1=xi2 mod N, where N=P×Q with P and Q both prime congruent to 3 modulo 4. The trapdoor (easy computation of xi from xi+1) is enabled with the knowledge of P and Q, which is the private key. Like other integer factorisation family primitives, the public key function has a smaller CPU load than the private computation enabled by the private key. In the time ticket sub-protocol, the higher CPU load is allocated to the client computer.

The size of the public key N is such that generating a fresh one is not a significant workload for the sporadic instances on client computers and arithmetic modulo N is not a significant CPU load on servers handling multiple time ticket sub-protocol instances. If these levels of CPU power demands can be reached in practice, the target security level has the following unusual definition.

From the above, a modulus size range from 224 to 320 bits (from 67 to 96 digits) seems adequate. A high limit is specified and set to a seemingly low value in order to protect the time ticket server from a CPU load induced by a desire to set every security level adjustment to its highest possible value.

5. Operating Principles

The time ticket sub-protocol specifies a time ticket server behavior that should withstand any remote party behavior, plus a legitimate client system participant behavior. The first aspect should be covered in isolation from the legitimate client behavior such that every corner cases are handled. But for sake of brevity, the two are combined here.

First the client computer creates a fresh BBS modulus N.

Client Network Server

Create a fresh BBS modulus N.

----- N ----->

Check N for size and odd value.

Select random x0 with sqrt(N)<x0<N; let xi=xi-12 mod N for i from 1 to 3.

Recover x2 and x1 from x3.

<----- x3,t0,t -----

Note current time t0; select client scheduled time t from current traffic load.

Keep <N,x1,x2,t> in some heap memory, indexed by N, aborting for duplicate N.

Wait until time t or for a duration t-t0.

----- N,x2 ----->

Retrieve <N,x1,x2,t> from heap memory, indexed by N; abort unless it exists and not yet used, current time is past t, and received x2 matches retrieved x2.

Mark <N,x1,x2,t> as used.

Select random response resp and send <x1,resp> to application server.

Recover resp from x1 XOR resp and x1.

<----- x1 XOR resp -----

Obfuscate response as x1 XOR resp.

At the end of the sub-protocol, the client computer has been forced to wait a delay controlled by the time ticket server and the two sides share the time ticket value pair <x1,resp>.

A heap memory cleanup function is required in the time ticket server for older entries, or during a surge of new entries. Some denial of service management strategy is needed in the later case. This is part of the central mission of the time ticket server. Another delicate aspect is the selection strategy for the forced delay. A goal is to limit the pace at which the application server receives enrollment instances authorized by a valid time ticket.

In the application server, a time ticket value pair may be deleted once used by a client computer. Unused older entries must be cleaned up periodically. Because the client computer utility has no need to request a time ticket in advance, time tickets should have a short expiration time, e.g. no larger than 30 seconds. Otherwise an adversary would be in a position to stock a large number of time tickets and use them all at once in a denial of service attack. Or else an adversary might have the opportunity to factor N and steal unused time tickets before they expire. Also, it must be assumed that an adversary may spend the computational resources to learn random resp and x0 (with some ambguity) output by the server random source; thus the latter should resist cryptanalysis attempts.