- cypherpunks-legacy@lists.ogf.org

Re: Commercial PGP: Verifying Trustworthiness
by norm＠netcom.com 26 Aug '93

26 Aug '93

thug(a)phantom.com (Murdering Thug) writes: > I'm assuming the NSA will pressure ViaCrypt to put in a backdoor. One > possible backdoor that can be placed inside the commercial PGP and still > allow it to pass the above test is if commericial PGP secretly writes all > keys and pass phrases to a block on your hard disk, and marks that > block as used to the file system. In order to prevent you from scanning > your hard disk and finding that block, the information stored there could > be encrypted by a key which the NSA has in it's possession. At least the Commercial PGP is not tamper proof and examination can, in principle, discover the backdoor. After discovery it would impossible to deny.

1 0

Re: Source Code NOT available for ViaCrypt PGP
by norm＠netcom.com 26 Aug '93

26 Aug '93

Regarding Secret key generation. cme(a)ellisun.sw.stratus.com (Carl Ellison) says: > The only place to worry is with key generation, > both IDEA and RSA. I presume this is true. I include a Scheme program that finds the first prime in an arithmetic sequence. It uses a function published in Knuth. You can either study my program or compare its output with some program written by someone else to the same spec. If people are interested I will annotate the code and its output better. As it is now the prime that it finds is the last number that it outputs before it stops. Curiously it has a probability of error which is large for small numbers but exceedingly small for large numbers, just the opposite of human testers. I claim that this is a good specification for choosing your secret primes. It has a slight advantage over merely finding the first prime beyond some specified number because that tends to find primes that follow long runs of composites. It just now (as I edited this) found the prime 1000000000000000 00000000000000000000000000000000000000000000000000000000000000913 as the first prime in the sequence 10^80+11*n. I typed (scan (expt 10 80) 11) to the interpreter to get this. It took several minutes. I used MacGambit on a 68030. The output theoretically depends on the hokey random number generator here but if two implementations yield different answers due to different random number generators Knuth and others would be very interested! For use in real RSA application we should include a function that hashes typed in text into a bignum. A good hash of long text is a very good random number! It need not be a crypto hash! (define (ex x)(write x)x) (define (rand31 seed) (lambda()(let* ((hi (quotient seed 127773)) (lo (- seed (* 127773 hi)))(test (- (* 16807 lo) (* 2836 hi)))) (set! seed (if (> test 0) test (+ test 2147483647))) seed))) (define (gbrand max seed)(let* ((rq (rand31 seed)) (nq (let v ((c max)(n 0))(if (< c (expt 2 31)) (cons (let w ((cx c)(nx 1))(if (< cx 2) nx (w (quotient cx 2)(+ nx 1))))n) (v (quotient c (expt 2 31))(+ n 1))))) (z (car nq))(n (cdr nq))(k (+ (* 31 n) z))) (write(list max k z n)) ; max, k, n, z, L and m are non-negative integers. ; 2^(k-1)<=max<2^k. k=31*n+z. 0<z<=31. ; I claim this code is efficient if ; (quotient .. (expt 2 ..)) and (modulo .. (expt 2 ..)) are efficient. (if (= n 0)(lambda () (let r ()(let ((q (modulo (rq) (expt 2 z)))) (if (< q max) q (r))))) (let ((L (quotient max (expt 2 (- k 31)))))(write L) ; max = L*2^(k-31) + m; 0<=m<2^(k-31). L is the high 31 bits of max. (lambda()(+ (* (expt 2 z)(let g ((nx n))(if (= nx 1) (let r ()(let ((q (rq)))(if (< q L) q (r)))) (+ (* (expt 2 31)(g (- nx 1)))(rq)))))(modulo (rq)(expt 2 z)))))))) (load "Random.scm") (define ww (lambda(n x)(display (list n x)) x)) ; The following definition is to ensure that modulo never ; produces negative numbers. (define modulo (let ((modulo modulo))(lambda (a m) (if (negative? a) (- (- m 1) (modulo (-(- m 1) a) m)) (if (positive? a) (modulo a m) 0))))) ; The following is the "Jacobi Symbol". (a|P) (define (j a P) (if (< a 2) (if (= a 1) 1 (if (= a 0) 0 (j (modulo a P) P))) (if (>= a P) (j (modulo a P) P) (if (even? a) (let((q (j (/ a 2) P)) (m (modulo P 8))) (if (or (= m 3)(= m 5))(- q) q)) (let((q (j (modulo P a) a))) (if(or (= (modulo P 4) 1) (= (modulo a 4) 1)) q (- q))))))) (define (mod-exp b p m)(cond ((= p 0) 1) ((even? p)(let ((x (mod-exp b (/ p 2) m)))(modulo (* x x)m))) (#t (modulo (* b (mod-exp b (- p 1) m)) m)))) ; The following is by Solovay & Strassen as presented in Knuth page 396. (define (p-test a P)(if(zero? a)(cdr 2))(and (odd? P) (= (gcd a P) 1) (zero? (modulo (- (j a P)(mod-exp a (/(- P 1) 2) P)) P)))) (quote "The function scan below returns the first prime in the") (quote "arithmetic sequence a + n*b") (define (scan a b)(let* ((g (gcd a b))(n (modulo b 210)) (random (gbrand (+ a (if (positive? b) 0 (* 2000 b))) 228765)) (probe (+ 1 (random)))) (if (> g 1) (list "Always divisible by" g) (let more ((a1 a)(m (modulo a 210))(cn 0)) (if (and (let all ((l (list 2 3 5 7)))(or (null? l) (and (positive? (remainder m (car l))) (all (cdr l))))) (let all ((l 20)(p probe)) (or (zero? l) (and (ww cn (pt p a1)) (all (- l 1)(+ 1 (random))))))) a1 (begin (display ",")(more (+ a1 b)(modulo (+ m n) 210)(+ cn 1)))))))) (define (pc wx) (let zz ((q (- wx 1))(s 0))(if (zero? q) s (zz (- q 1)(+ (if (p-test q wx) 1 0) s))))) ; The following prmality test is from second edition of ; volume 2 of Knuth's "The Art of Computer Programming", ; page 379. (define (pt x n) (or (= n 2) (let* ((pr (let z ((q (- n 1))(k 0))(if (odd? q)(cons q k) (z (quotient q 2)(+ k 1))))) (q (car pr))(k (cdr pr))(nm1 (- n 1))) (let lp ((j 0)(y (mod-exp x q n))) (or (and (= j 0)(= y 1)) (= y nm1) (and (< (+ j 1) k)(lp (+ j 1)(modulo (* y y) n)))))))) ; 10^100-797, 10^200-189, 10^299-171, 10^300-69 are prime. ~. ~.

1 0

Re: Source Code NOT available for ViaCrypt PGP
by smb＠research.att.com 26 Aug '93

26 Aug '93

btw, how did they get around PKP's rule about using the interface provided which uses DES ? That rule applies to RSAREF, and not necessarily to anything else.

1 0

Further PGP Security Doubts
by an31144＠anon.penet.fi 26 Aug '93

26 Aug '93

> 4) It's not too hard to build a test-suite for PGP to ensure it's > implementation of IDEA is correct, and it's possible to check > it's key generation/session key generation things. Of course > key management isn't too big a deal either... Thus I don't > think it requires too great an effort to trust ViaCrypt. > And if not - buy their copy to stay legal and use the > Source to be safe (:-). I would be pleased to see some truly exhaustive efforts made to test PGP's actual security. I have been seeing yet more criticisms of PGP, this time from some character calling himself "Raymond Paquin." He claims to be a professor of mathematics who has been working at an unnamed university exclusively on cryptographics for the past twelve years. He implies that he is working for some government in a classified capacity and is thus unable to either publish or discuss the matter openly. He claims that PGP is fatally flawed, though the flaw is in niether RSA or IDEA, but rather somewhere within the PGP part of the program. Copping the "I can say no more! I have said too much already!" melodrama, no more detailed information is forthcoming. Now, this tease seems to reek of a hoax, but Zimmermann himself claimed no high degree of security for the program. To my knowledge, no serious or well-funded unclassified attempts have been made to crack PGP. I fear that we are putting our faith in snake oil, as Zimmermann puts it. I am not a mathematician, but merely a former spear-carrier in the Cold War with some fairly well-developed residual instincts about this sort of thing, including a conviction that all security measures - physical, electronic or cryptographic - can be compromised by a determined opponent with extensive resources. Once compromised, attacks thereafter may often be trivially accomplished.

1 0

Visa, HNC Inc. develop neural network as a weapon to fight fraud
by Andy Wilson 26 Aug '93

26 Aug '93

Date: Wed, 25 Aug 93 22:02:04 -0600 From: "L. Detweiler" <ld231782(a)longs.lance.colostate.edu> [...] Furthermore, a `warning flag' system is potentially superior to the current system, contrary to your statement of it being a `problem' in that potentially no other information other than `suspicious activity alert' is provided. as P. Wayner indicated, the potential for simple PR is increased to the point that at least some customers are pleased. I did not intend to imply that Visa's policy in particular was not to use the neural network as a "warning flag". I was merely pointing out potential problems in the trend of using neural networks to make decisions based on personal information, including details of neural network technology that limit their usefulness as "warning flags". I was not commenting on the policies of Visa, Inc., of which I have no personal knowledge. The use of AI technology by both businesses and the government to track personal and corporate transactions is a major trend. A former colleague who is doing classified work along this line referred to what he was doing as "building big brother." Andy

1 0

Visa, HNC Inc. develop neural network as a weapon to fight fraud
by strick -- henry strickland 26 Aug '93

26 Aug '93

Extracted from "FC NEWSBYTES 1.3", David Geddes <dgeddes(a)NETCOM.COM> Editor, where FC = FutureCulture mailing list <FUTUREC-request(a)UAFSYSB.UARK.EDU>. strick ____________________________________________ _ _.......... B Y T E 4: Visa, HNC Inc. develop neural network as a weapon to fight fraud SAN FRANCISCO (AUG. 10) PR NEWSWIRE - Visa International and HNC Inc. have announced a strategic agreement to develop a comprehensive merchant risk detection system. The new system will be designed to better control fraud at the merchant level by determining the risk associated with individual card transactions. This agreement continues to support Visa International's active role in developing effective solutions to the problem of fraud occurring at the point of sale. The merchant risk detection system will be available in 1994. "Visa has combined its core systems capabilities and the premier technology available -- neural networks -- for fighting credit card fraud," explained Roger Peirce, Visa International's executive vice president, Delivery Systems. "HNC, an industry leader in neural network applications and credit card control services, is a logical partner for Visa," he added. Michael A. Thiemann, HNC's executive vice president, called the agreement "another example of our commitment to solving tough business problems through the application of cutting-edge technologies." Neural network technology enables a system to predict the probability of fraud by learning from a large number of past transactions, both legitimate and fraudulent. By using neural networks to its full extent, Visa will be able to provide superior risk analysis for its members. In combating credit and debit card fraud, Visa already has developed several programs utilizing information gained from neural network research. Worldwide implementation of the International Points-of- Compromise (IPOC) program has proved highly effective for identifying merchant locations that may be selling or giving account information to counterfeiters. Another successful program, called the Central Deposit Monitoring (CDM) program, matches merchant activity with sales draft laundering characteristics and identifies unusual merchant deposits. In addition, close cooperation with law enforcement agencies and legislatures enhances the value of the programs which, in turn, allow Visa members to pass on the protection to its cardholders and merchants. The planned Visa-HNC merchant risk detection system is designed to further reduce fraud losses by assigning a risk score to each authorization transaction processed through the VisaNet systems. "With this new system, members will be better able to assess risk at the point- of-transaction and, therefore, make more informed authorization decisions," confirmed Peirce. According to The Nilson Report, merchant fraud worldwide cost the financial industry an estimated US $689 million in 1992. HNC will integrate the risk score into Falcon(TM), their existing, real-time credit card fraud-detection system that runs at card issuer sites to identify and prevent a wide range of fraud at the cardholder level. It determines the probability of fraud on each credit card authorization by comparing it to the cardholder's purchase patterns and the latest trends in credit card fraud. Introduced in September 1992, Falcon has already achieved success in reducing fraud losses of major credit card issuers. HNC Inc., the world's leader in the application of neural networks, develops, sells, integrates and supports advanced decision solutions based on neural network and statistical technology. HNC provides practical products and services to the financial, credit card, debit card, merchant services, insurance, mortgage underwriting, retail and direct marketing industries. Visa is the leading consumer payment system in the world with more than 10.4 million acceptance locations, the largest global ATM network and 309 million cards issued worldwide. -0- 8/10/93 /CONTACT: Gail Murayama of Visa International, 415-570-3645; or Ken Jones of HNC Inc., 619-546-8877 ____________________________________________ _ _..........

3 5

ViaCrypt's PGP
by Read me doctor memory! 26-Aug-1993 1434 26 Aug '93

26 Aug '93

Thug(a)phantom.com says: >I'm assuming the NSA will pressure ViaCrypt to put in a backdoor. One >possible backdoor that can be placed inside the commercial PGP and still >allow it to pass the above test is if commericial PGP secretly writes all >keys and pass phrases to a block on your hard disk, and marks that >block as used to the file system. In order to prevent you from scanning >your hard disk and finding that block, the information stored there could >be encrypted by a key which the NSA has in it's possession. There's actually a much easier way for a backdoor to be inserted that will allow monitoring even without the spooks knocking on your door to get your disk... PGP uses RSA only to encode and transmit a "random" DES/IDEA-type session key, and the rest of the message is encoded only with the session key. The recipient PGP uses RSA to recover the session key, and then decodes the rest of the message with the recovered session key. Say that the "backdoored" PGP is redesigned to only choose session keys from a large-but-reasonably-brute-forceable set.... [example: only from consecutive 8-byte sequences in the executable image; I'm sure some other more obscure method can be easily devised]. The result is that there might only be a few hundred thousand possible session keys- few enough that a brute-force attack with a small array of workstations might succeed in recovering the session key in a few minutes to hours. ----- The only way ViaCrypt can prove that this isn't the case is to distribute the source code of _their_ product. [Note: they do NOT have to include the RSA module source- if it's possible to examine the non-RSA code, and instrument it (to prove that the session key is honestly generated _AND_ transmitted/recovered correctly) then Thug's tests will be adequate to verify a lack of backdoors (as far as I can see- but I'm perhaps not as devious as a professional). -Bill

2 1

Re: Source Code NOT available for ViaCrypt PGP
by norm＠netcom.com 26 Aug '93

26 Aug '93

The proper paranoid must worry whether the licenced PGP does what it is supposed to do. One can compare the output of the ViaCrypt PGP with that of the current version. Discrepencies would merit great suspicion and perhaps disassembly. Improper paranoids might be comforted in the knowledge that many proper paranoids were comparing the two versions. I have not studied the format of the PGP output. Is it possible for the ViaCrypt PGP to interoperate with the current version unless it comforms completely? We must clearly worry about undocumented new formats. Incedently why do the code owners trust the customer to not illegitamitely copy the binary program, but not trust the customer to not illegitamitely copy the source program?

1 0

Re: blinding & PGP
by Karl Lui Barrus 26 Aug '93

26 Aug '93

It occured to me over lunch that PGP IDEA encrypts files; what is RSA encrypted are session keys, hashes, etc. So you never really digitally sign the file itself, you instead digitally sign the portion that contains the session key used, hashes and so forth. Again, I'm sure PGP doesn't blind the RSA portion, so I would say you can't bamboozle someone into signing a blinded document with PGP. Now, as for verifying a commercial version of PGP by comparing encrypts... it all depends on how exactly randseed.bin figures into the session key creation. Two files encrypted with the same public key could compare very differently if the random session keys are different, since the IDEA encryptions would differ and the so would the MD5 hashes, and so forth. I'm not sure if additional info besides the randseed.bin file goes into session key creation. -- /--------------------------------------------------\ | Karl L. Barrus | | klbarrus(a)owlnet.rice.edu | | D1 59 9D 48 72 E9 19 D5 3D F3 93 7E 81 B5 CC 32 | \--------------------------------------------------/

1 0

PROTOCOL: Encrypted open books
by Eric Hughes 26 Aug '93

26 Aug '93

Note: I started this reply last week; I've decided to post what I know, since I don't have a solution and I've run out of simple ideas for now. Hal' criticism that (real) money could leak out of the system is correct. The problem is that while the books would still balance, i.e. sum to zero, some fake depositor would have a negative balance, the net result of taking out more money than you put in. Negative numbers just aren't allowed in double-entry bookkeeping, but they were allowed in the first protocol set. The first part of the solution is to allow no private accounts on the left hand (asset) side of the ledger, in other words, no anonymous loans. A protocol for doing anonymous loans could be invented, but since the first problem is merely to run a money exchange and not more complicated financial services, this is acceptable. Most of the money that left the S&L's was by corrupt loan practices, so I don't consider this omission a particularly glaring one right now. Therefore all the private accounts must be on the right hand side, that is, they are all liabilities. In layman's terms, the bank owes you; should you ask for your money, they have to give it to you. If we can verify that each of these accounts never goes negative, then we can be certain that if the books balance, that the amounts of money in each account are accurate. Consider this. If money was transferred from your account to another one, that transaction shows up in the public encrypted transaction record. If you have due diligence over this record, you can assertain that no transaction was performed against your will. This case corresponds to a debit and credit against two customer accounts, decreasing one and increasing the other. Another way that money might end up in a fake account if it were credited with assets. A debit to an asset increase its value and the credit to the account increases that value. This is the case of a deposit; the bank gets cash (+asset) and credits someone's account (+account). Now if they want to give someone money this way, they have to do so by increasing the assets somehow; in other words, they money has to come from somewhere. It didn't come from any of the customers because they've already verified that. It didn't magically appear from one of the other asset accounts because these are all publically audited. In summary, we need to ensure that all accounts have positive balance. Public accounts can be revealed and seen to be positive. Private accounts need a cryptographic assurance. A private account starts off at zero. This can be publically revealed. Then to the encrypted transaction log and the public cyclic balances we add publication of the private balances in encrypted form that allows us to verify to the blinded balance is positive. This balance is verifiably linked to previous cyclic balances via the transaction log. It is therefore linked all the way back to the beginning balance which was zero. Consider all the transaction triples for which the first element is equal to the private account in question, since the account was opened. Take a product of all of the second elements and a product of all the third elements. It is clear that these products can be calculated inductively from the previous cyclic products and the activity in this cycle. The products on second and third elements are equal to g^( Sum x_i,j,t + Sum r_i,j,t ), h^( Sum r_i,j,t ) where I've added a time index by cycle which was implicit before. The notation for the inductive calculation is different, of course, and also obscures the underlying invariant. What we want is a certificate that Sum x_i,j,t is positive. Here it gets a bit hairy. There are likely other solutions to this technical requirement; here is the one I thought up yesterday and today. I thought I had an idea with promise on how to create such certificates using quadratic residuosity, but it doesn't work. I'm still thinking about it; this certificate doesn't seem impossible to create, but the standard ideas that I know about in algebraic protocol design don't seem to work. If anybody wants to work on this technical point off-line with me, send me mail. The math involved is advanced enough that I'd prefer to post summaries of work rather than all the detailed discussion. Another non-technical attack on the problem is to require periodic bank holidays, where all private balances will be revealed to be zero (preferably), or whatever is actually in the account. This doesn't prevent owner fraud, but does put an upper bound on the time in which to perpetrate it. Eric

1 0