[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

*To*: [email protected]*Subject*: Secure versus ?*From*: [email protected]*Date*: Tue, 05 Dec 1995 11:52:37 EST*Cc*: [email protected]*Sender*: [email protected]

Thanks to everybody who replied to my previous message. As most of you suspected, it turned out to be possible to break the permutations I was using. The reason why I have pursued this despite its non-intuitiveness is that the following well known protocol also seems to have the same property I claimed. Please tell me how a computationally unbounded adversary could defeat the following: (without active attack against which this immediatelly fails (i.e. it has to be combined with an authentication algorithm)). Please help me, this problem is totally driving me crazy! A VARIATION OF SHAMIR'S THREE PASS PROTOCOL SAFE FROM PASSIVE ATTACK BY A COMPUTATIONALLY UNBOUNDED ADVERSARY: Alice wants to send Bob a message. She is going to send her message a fraction of a bit of a time via the following protocol. Before hand: 1. Enumerate all the primes from 256 to 511. Call them N. 2. For each prime, enumerate all the numbers less than it that are also relatively prime to N-1. Call these E. 3. Number each pair of E and N. The algorithm can be divided into an inner loop and an outer loop. The outer loop calls the inner loop. Inner Loop: Alice wants to use the inner loop to send bit b. 1. Alice randomly chooses seven bits of salt, and prepends b to them creating an 8 bit M 2. Alice randomly chooses an (Na,Ea) pair from the list of possibilities. 3. Alice calculates D such that E*D mod (N-1) equals 1 4. Bob randomly chooses an (Nb,Eb) pair from the list of possibilities. 5. Bob calculates D 6. Alice sends Bob the nine bit number (M^Ea) mod Na = C1 7. Bob sends Alice (C1^Eb) mod Nb = C2 8. Alice sends Bob (C2^Da) mod Na = C3 9. Bob calculates (C3^Db) mod Nb = M, the bit being the MSB. The unbounded passive adversary calculates a probability (p) between 0.5 and one with which he/she can guess the bit. This is based on the facts that 1. only a fraction of all pairs of Na and Ea will map C2 to C3, 2. only a fraction of all pairs of Nb and Eb will map C1 to C2, 3. only a fraction of all Na are high enough to produce C1. With thousands of transform pairs, there are more bits of entropy in the transform and salt selection, than there is information in the three messages. Alice, Bob and Eve can thus know what p is. Outer Loop: 1. Alice sends Bob an initialization vector using the inner loop. 2. Alice uses the inner loop to send Bob a series of bits. Each bit is either a random bit or the next bit of the message depending what the value of p for the previous inner loop was. A simple proper (but VERY INEFFICIENT) outer loop algorithm would be the following: Alice: 1. If the p for the previous inner loop was 0.5, send the XOR of the message and the previously sent bit. 2. If the p for the previous message was not 0.5, send a random bit. Bob: 1. If the p for the previous message was 0.5, take the bit, XOR with the previous bit, and append it to the message. 2. Otherwise just save the bit for one more itteration. PLEASE help me. I CAN'T find how this fails to be information-theoretically secure, but I am convinced that it should not be possible to do this, and I have been absolutely unproductive at anything since I first started working on this. Cheers, Jason W. Solinsky

**Follow-Ups**:**Re: Secure versus ?***From:*Robbie Gates <[email protected]>

- Prev by Date:
**Re: Info on Netscape's key escrow position** - Next by Date:
**Re: No Privacy Right on "My" Desktop ?** - Prev by thread:
**ZD Net Update v.1 #2** - Next by thread:
**Re: Secure versus ?** - Index(es):