Últimos Cambios
|
|
|
|
Últimos Cambios |
|
|
|
||
| Mi estado actual
en Jabber/XMPP:
| |||
Última Actualización: 11 de Mayo de 1.998 - Lunes
Message-ID: <3536295B.7CFE@argo.es> Date: Thu, 16 Apr 1998 17:52:59 +0200 From: Jesús Cea Avión <jcea@argo.es> To: hacking@argo.es, anita@argo.es, teleco-vigo@argo.es, gdi@uvigo.es, apedanica@encomix.es, free-miembros@arnal.es, ircops@esnet.org Subject: ¡¡¡El GSM cae!!!
¡¡¡Por fin!!!. Una vez más se demuestra que el oscurantismo no ayuda a mantener un "secreto" a salvo.
Ya es posible clonar tarjetas SIM (Subscriber Identity Module). Es decir, hacerse pasar por cualquier usuario GSM. No hace falta modificar el móvil, ya que los móviles son universales y la identidad la proporcionan las tarjetas.
En este mensaje intentaré recopilar y ordenar un poco la furibunda cantidad de mensajes que estoy recibiendo desde hace un par de días, especialmente en las listas de cypherpunks y criptografía. En Bugtraq apenas ha salido una reseña :).
El anuncio inicial se hizo el Pasado Lunes 13, en las listas cypherpunks@algebra.com y cryptography@c2.net:
The Smartcard Developer Association (SDA) and two U.C. Berkeley researchers jointly announced today that digital GSM cellphones are susceptible to cloning, contrary to the belief of even the telecommunication providers that have fielded them.
[...]
One of the discoveries that the SDA made about GSM security was a deliberate weakening of the confidentiality cipher used to keep eavesdroppers from listening to a conversation. This cipher, called A5, has a 64 bit key, but only 54 bits of which are used. The other ten bits are simply replaced with zeros.
[...]See http://www.scard.org/ for more info.
[Special thanks to Tim Hudson for authoring the smartcard interface code that made our work possible. We wouldn't have achieved what we did it with out it].
Este mensaje ha creado una cascada de respuestas. Las voy almacenando todas en una carpeta del Netscape y, de momento, tengo 189 mensajes, eliminando duplicados y superfluos :). Intentaré resumir las conclusiones, provisionales, en este mensaje.
La página original del ataque está en http://www.scard.org/.
Han salido también diversas notas de prensa sobre el asunto:
Se puede encontrar una descripción técnica del ataque en:
From sci.crypt Fri Jun 17 17:11:49 1994 From: rja14@cl.cam.ac.uk (Ross Anderson) Date: 17 Jun 1994 13:43:28 GMT Newsgroups: sci.crypt,alt.security,uk.telecom Subject: A5 (Was: HACKING DIGITAL PHONES)The GSM encryption algorithm, A5, is not much good. Its effective key length is at most five bytes; and anyone with the time and energy to look for faster attacks can find source code for it at the bottom of this post.
The politics of all this is bizarre. Readers may recall that there was a fuss last year about whether GSM phones could be exported to the Middle East; the official line then was that A5 was too good for the likes of Saddam Hussein.
However, a couple of weeks ago, they switched from saying that A5 was too strong to disclose, to saying that it was too weak to disclose! The government line now pleads that discussing it might harm export sales.
Maybe all the fuss was just a ploy to get Saddam to buy A5 chips on the black market; but Occam's razor suggests that we are really seeing the results of the usual blundering, infighting and incompetence of bloated government departments.
Indeed, my spies inform me that there was a terrific row between the NATO signals agencies in the mid 1980's over whether GSM encryption should be strong or not. The Germans said it should be, as they shared a long border with the Evil Empire; but the other countries didn't feel this way, and the algorithm as now fielded is a French design.
A5 is a stream cipher, and the keystream is the xor of three clock controlled registers. The clock control of each register is that register's own middle bit, xor'ed with a threshold function of the middle bits of all three registers (ie if two or more of the middle bits are 1, then invert each of these bits; otherwise just use them as they are). The register lengths are 19, 22 and 23, and all the feedback polynomials are sparse.
Readers will note that there is a trivial 2^40 attack (guess the contents of registers 1 and 2, work out register 3 from the keystream, and then step on to check whether the guess was right). 2^40 trial encryptions could take weeks on a workstation, but the low gate count of the algorithm means that a Xilinx chip can easily be programmed to do keysearch, and an A5 cracker might have a few dozen of these running at maybe 2 keys per microsecond each. Of course, if all you want to do is break the Royal Family's keys for sale to News International, then software would do fine.
It is thus clear that A5 should be free of all export controls, just like CDMF and the 40-bit versions of RC2 and RC4.
Indeed, there seems to be an even faster attack. As the clock control is stop-go rather than 1-2, one would expect some kind of correlation attack to be possible, and on June 3rd, Dr Simon Shepherd of Bradford University was due to present an attack on A5 to an IEE colloquium in London. However, his talk was spiked at the last minute by GCHQ, and all we know about his attack is:
- that sparse matrix techniques are used to reconstruct the initial state (this was published as a `trailer' in the April 93 `Mobile Europe');
- that he used some of the tricks from my paper `Solving a class of stream ciphers' (Cryptologia XIV no 3 [July 90] pp 285 - 288) and from the follow-up paper `Divide and conquer attacks on certain classes of stream ciphers' by Ed Dawson and Andy Clark (Cryptologia XVIII no 1 [Jan 94] pp 25 - 40) (he mentioned this to me on the phone).
I believe that we have to stand up for academic freedom, and I hope that placing A5 in the public domain will lead to the embargo on Simon's paper being lifted.
Ross Anderson
APPENDIX - AN IMPLEMENTATION OF A5
The documentation we have, which arrived anonymously in two brown envelopes, is incomplete; we do not know the feedback taps of registers 2 and 3, but we do know from the chip's gate count that they have at most 6 feedback taps between them.
Message-ID: <3540CAB1.2BBB@argo.es> Date: Fri, 24 Apr 1998 19:24:01 +0200 From: Jesús Cea Avión <jcea@argo.es> To: hacking@argo.es, anita@argo.es, teleco-vigo@argo.es, gdi@uvigo.es, apedanica@encomix.es, free-miembros@arnal.es, ircops@esnet.org, cert-es@listserv.rediris.es Subject: ¡¡¡El GSM cae!!! (y 2) References: <3536295B.7CFE@argo.es>
Este mensaje intenta complementar el texto que envié hace unos días.
GSM Alliance Clarifies False & Misleading Reports of Digital Phone Cloning
GSM Remains the Most Secure Commercial Wireless Technology
(Business Wire; 04/17/98)A coalition of wireless Personal Communications Services (PCS) providers has released [on 17 Apr 1998] facts to correct some misconceptions generated by the recent claim that several California researchers had found a weakness in the security of Global System for Mobile communications (GSM) technology, the world's most popular digital wireless standard.
The North American GSM Alliance, LLC - consisting of the eight largest GSM network operators in the United States and Canada - provided the following information in response to a number of erroneous published reports.
1. GSM phones are not vulnerable to cloning.
Researchers only claimed that, through a process of trial and error, they figured out how to copy information from the Subscriber Identity Module (SIM) card - a unique GSM feature that contains a customer's individual network access code. Duplicating a SIM card is not like cellular cloning since the network only recognizes one copy of a GSM phone number at a time. This is an important distinction, since it does not permit would-be thieves to fraudulently capture, duplicate and utilize a customer's phone number and account information by intercepting over-the-air transmissions and deciphering the data.
By contrast, information from ordinary analog cellular phones can be pulled out of the airwaves, copied and re-used multiple times. This illegal process, also known as "sniffing," is still not possible to do with GSM technology. The California group said that it needed physical access to a SIM card in order to duplicate it. While they believed copying theoretically could be done remotely, the group admitted that it was, in fact, unable to do so.
2. There is no risk to subscribers.
GSM's design process and proven functionality continues to offer the strongest level of commercial wireless security. GSM customers can have the highest degree of confidence that they are protected from over-the-air cloning.
In fact, thieves can more easily steal GSM phone service simply by stealing wireless handsets rather than producing counterfeit SIM cards. Once someone steals a SIM card, there's no need to copy it. The notion is as ridiculous as a someone stealing an armored car full of money, then copying the bills inside! And since the GSM networks allow only one call at a time from any phone number, having multiple copies of a SIM is worthless. As an additional level of security GSM operators have procedures in place which would quickly detect and shut down attempted use of duplicate SIM card codes on multiple phones.
Nevertheless, customers should protect their wireless phones and SIM cards the same way they would protect their wallets and bank cards. Subscribers who lose their phone or SIM card should report it immediately to their wireless service company. The lost or stolen SIM can be de-activated to prevent others from using the account.
3. There is no risk of over-the-air eavesdropping.
The level of encryption used by GSM makes over-the-air eavesdropping nearly impossible. So far, no one claims that they can listen to the content of conversations or monitor data transmitted over the air on the GSM network, including governments and network operators. Confidentiality of GSM customer conversations remains intact and uncompromised.
4. The ability to copy a SIM card is nothing new.
It was always known that this could be done. Last weekend's announcement is really no different from processes GSM providers use all the time to encode smart chips. For several years now, educational institutions and scientific laboratories have demonstrated the capability to extract data from, and copy, smart cards. But it is an extremely complex task and would not be practical for stealing wireless phone service. Besides, even if a handset or SIM card were stolen, GSM operators have the ability and technological tools to shut down fraudulent service quickly.
5. The key code which protects a subscriber identity is not "fatally flawed."
This is a somewhat complicated subject. There are two different key codes: first, an authentication code - the A3 algorithm- that protects the customer's identity; second, an encryption code - the A5 algorithm - that ensures the confidentiality of conversations. It has been alleged that the authentication code (A3 algorithm) is weakened because only 54 of the 64 bits are used, with 10 bits being replaced by zeroes. In reality, those final 10 bits provide operators with added flexibility in responding to security and fraud threats. Additionally, the GSM algorithm that the researchers claimed to have broken is the "example" version provided by the international organization that governs the use of GSM technology to its approved carriers for them to create their own individual version. It may not be what is deployed in the market. Several operators have already decided to customize their codes, making them more sophisticated.
There has been some confusion about the various types of code used by GSM. In addition to the 64-bit authentication cipher, there is a more powerful voice encryption code (A5 algorithm) which helps keep eavesdroppers from listening to a conversation. This code was not involved in last weekend's announcement. Also, the speculation that GSM's encryption algorithms have been deliberately weakened because of pressure by the U.S. intelligence community is absolutely false.
Conclusion
While no human-made technology is perfect, customers can still rely on the privacy features and security of GSM's transmission technology. It remains the most secure commercial wireless communications system available today. More than 80 million customers in 110 countries use GSM phones and not one handset has been cloned since the first commercial service was launched in 1992.
North American GSM Alliance, L.L.C. is a consortium of U.S. and Canadian digital wireless PCS carriers, which helps provide seamless wireless communications for their customers, whether at home, in more than 1,000 U.S. and Canadian cities and towns, or abroad. Using Global Systems for Mobile (GSM) communications, GSM companies provide superior voice clarity, unparalleled security and leading-edge wireless voice, data and fax features for customers. Current members of the GSM Alliance include: Aerial Communications, Inc., BellSouth Mobility DCS, Cook-Inlet Western Wireless; Microcell Telecommunications Inc., Omnipoint Communications, LLC, Pacific Bell Mobile Services, Powertel, Inc., and Western Wireless, Corp., which continue to operate their own businesses and market under their own names.
CONTACT: For Additional Information:
Terry Phillips, Omnipoint, (973) 290-2533 OR
Mike Houghton, Communicreate, (703) 799-7383
Me gustaría puntualizar la nota de prensa, casi párrafo por párrafo:
Aún asumiendo que la red fuese capaz de detectar la existencia de dos SIM idénticas, impidiendo de esta forma el "fraude", nada imposibilita que el poseedor de la tarjeta SIM duplicada la utilice exclusivamente durante las horas en las que el abonado legítimo tiene el móvil apagado (por ejemplo, por la noche). También es posible, si existe esa "posibilidad de detección", realizar un efectivo ataque de denegación de servicio sobre el abonado legítimo, ya que la red no le permitiría enviar o recibir llamadas.
La nota de prensa indica que es ridículo duplicar una tarjeta SIM cuando ya se tiene acceso al original, aunque mi comentario anterior puede suponer una razón de "interés": las tarjetas, en el peor de los casos, son utilizables mientras el abonado legítimo tiene el teléfono apagado.
Existe un riesgo *MUY* importante: con una tarjeta "clonada" es trivial (y no detectable) descifrar las conversaciones cifradas con la tarjeta SIM original. Es decir, que se puede utilizar la tarjeta SIM clonada no para efectuar llamadas, sino para descifrar conversaciones.
Como se indica más adelante, los algoritmos de protección de la identidad del usuario y de la comunicación en sí, son diferentes. No obstante, la clave de uno se deduce del otro :-)). El documento http://jya.com/gsm061088.htm parece abonar la idea de que las claves de confidencialidad son derivadas de la clave de autentificación, que es precisamente lo que se ha atacado, y con éxito.
Además, tal y como se comentaba en mi mensaje anterior, queda abierta la posibilidad de que se pueda realizar el ataque sin disponer de la tarjeta física, enviando retos y recibiendo las respuestas de un teléfono en las inmediaciones.
Aquí, evidentemente, la alianza GSM se lava las manos. Dicen que la duplicación de tarjetas inteligentes no es algo nuevo. Naturalmente no indican que existen tarjetas inteligentes cuya razón última de existencia se basa, precisamente, en su capacidad de no ser duplicadas. Las tarjetas SIM caen dentro de este esquema, igual que lo hacen los monederos VISACASH, por ejemplo. A nadie se le ocurre que poder duplicar un monedero VISACASH con sus 10.000 pts de contenido, por ejemplo, tantas veces como se desee, es algo que no tiene importancia.
De nada sirve lo que se dice en el artículo: que la duplicación de una tarjeta SIM requiere unos medios fuera del alcance de las "personas normales". Al margen de que eso no resulta tranquilizador en absoluto, ni siquiera es cierto. Cualquiera con un ordenador y una interfaz chip (que uno se puede fabricar por menos de 500 pts) puede emular el ataque descrito en mi último mensaje.
Es cierto que los algoritmos A3, A8, etc., descritos es la
especificación GSM, son contenedores genéricos que no especifican
ningún algoritmo en particular. En la especificación se dan una serie de
algoritmos como "ejemplo", pero cada red GSM puede implementar los
suyos propios. Está en duda, no obstante, la motivación que una red GSM
tendría para adoptar algoritmos diferentes a los propuestos
"oficialmente" durante el desarrollo de la tecnología.
En http://jya.com/gsm061088.htm se comenta:
" In particular, there is no need for a common GSM authentication algorithm. and
different networks may use different algorithms. ( The algorithms do, however,
need to have the same input and output parameters; in particular, the length
of Kc is determined by the GSM cipher algorithm ). Never-the-less it is
desirable that there is a GSM standard authentication algorithm which may be used
by all networks which do not wish to develop a proprietary algorithm.
There is just one candidate for such an algorithm; it was proposed by the
German administration, and is analysed in Part VI of this report."
La frase clave es: "Never-the-less it is desirable that there is a GSM standard authentication algorithm which may be used by all networks which do not wish to develop a proprietary algorithm". ¿Cuántas redes GSM se habrán preocupado de desarrollar sus propios algoritmos, cuando ya se les daba uno como "ejemplo"?.
Por otra parte, la red es libre de elegir libremente los algoritmos A3 y A8, que son los que certifican la identidad del usuario y proporcionan la clave inical para la confidencialidad del resto de la comunicación. Esos algoritmos son libres, sin más restricciones que los fijados en el propio protocolo (longitud de clave, por ejemplo). Dichos algoritmos, por cierto, se ejecutan en la tarjeta, y no salen nunca de ella.
Sin embargo el algoritmo A5, que es el utilizado para cifrar la conversación, se ejecuta tanto en el móvil (no en la tarjeta) como en la red que está utilizando (para que la red pueda descifrar la conversación). Este algoritmo es FIJO para todas las redes GSM, asegurando así la compatibilidad entre todos los terminales y redes, posibilitando, por ejemplo, el "roaming" en cualquier red GSM del mundo.
En cualquier caso el ataque al A3 no se basa sólo en su reducida
seguridad (es realmente ridícula :), sino en que de los 64 bits que
componen su clave, sólo se utilizan 54. Ello supone reducir el espacio
de búsqueda 1024 veces. Es decir, que si el sistema fuera seguro (que
no lo es) y romperlo supone probar todas y cada una de las claves
posibles, y que -supongamos- hacerlo consume un AÑO trabajando 24 horas
al día, la reducción a 54 bits supondría poder encontrar la clave
correcta *NO* en un año, sino en un tiempo medio de cuatro horas, y un
tiempo máximo (en el peor caso) de OCHO HORAS Y MEDIA.
"In reality, those final 10 bits provide operators with added
flexibility in responding to security and fraud threats."
Me gustaría saber a qué amenazas de seguridad y fraude se refieren, y cómo es posible que reducir la seguridad del sistema mejore la "capacidad de respuesta" de los operadores...
Reeditar nuevas tarjetas SIM empleando algoritmos A3 y A8 más seguros, en vez del COMP128. Este cambio no supone ninguna modificación ni en los terminales móviles ni en la red, salvo en el sistema central de autentificación (puede haber un par de ellos en toda una red GSM). El único coste sería el derivado de crear y distribuir las nuevas tarjetas.
Esto es algo a lo que, simplemente, no se puede cerrar los ojos.
Message-ID: <3544C005.5E6A@argo.es> Date: Mon, 27 Apr 1998 19:27:33 +0200 From: Jesús Cea Avión <jcea@argo.es> To: Temas de Seguridad en Redes <CERT-ES@LISTSERV.REDIRIS.ES> Subject: Re: Más GSM References: <01BD71E0.670A8E80@grendel.ls.fi.upm.es>> Vale, clono una tarjeta GSM y la puedo usar para hacer llamadas
Evidentemente sí :).
A ver, te cuento...
CLAVE1=CLAVE.
Como puede verse, el conocimiento de los "secretos" está sólo en la central de autentificación y en el SIM. Cuando la estación base (que puede ser de otra compañía) solicita un trío de valores, la central de autentificación genera un valor aleatorio para RETO, lo cifra usando A3/A8 y la clave secreta del usuario, para obtener RESPUESTA y CLAVE.
Espero que esta explicación haya dejado claro, en primer lugar, cómo funciona el "roaming" :) y, en segundo lugar, que conociendo los algoritmos A3, A8 y A5 (que aunque eran confidenciales inicialmente, hoy en día son de dominio público) y la clave secreta del SIM, es posible tanto hacerse pasar por el usuario como descifrar sus conversaciones.
Esto último es muy sencillo. Simplemente hay que espiar el registro del móvil en la red, cuando se enciende. En dicho registro la estación base envía RETO. Nosotros lo "escuchamos" con nuestra SIM duplicada, y a partir de él (y de la clave secreta) podemos obtener CLAVE, que será la clave que el móvil y la estación base utilizarán para "asegurar" la privacidad de la comunicación.
Si hay alguna duda...
La información que sigue no la he enviado con anterioridad en ninguna lista de correo. Es inédita :-):
Bethesda, Md.-based Omnipoint Corp. said it plans to change the mathematical formulas used in its wireless phone service after two UC Berkeley researchers discovered a way to break the code that protects it. Omnipoint Executive Vice President George Schmitt said he's going to personalize Omnipoint's formula for identifying phones rather than use the general formulas of the global system for mobile communications, or GSM, digital wireless standard. Tim Ayers, a spokesman for the Cellular Telephone Industry Assn., said he expects most GSM operators to follow Omnipoint's lead. [...]
Naturalmente no se dice que algoritmos se van a utilizar como A3/A8, lo que sólo significa que la comunidad investigadora no podrá investigarlos a fondo antes de ser distribuídos en las nuevas tarjetas SIM. Es decir, que nada garantiza que el nuevo esquema, no público, no tenga otro error de diseño como el que hizo posible el ataque al COMP128.
Message-ID: <m0ySMLJ-0003b8C@ulf.mali.sub.org> Date: Thu, 23 Apr 98 15:47 +0200 From: ulf@fitug.de (Ulf Moller) To: ukcrypto@maillist.ox.ac.uk Subject: Re: More on A5 strength In-Reply-To: <wxyax54fno.fsf@polysynaptic.iq.org> CC: cryptography@c2.net
Julian Assange
>I haven't read Ross's [45] - I doubt it is about A5 per se, but rather
The excerpt of the leaked GSM Security Study at
http://jya.com/gsm061088.htm contains an incomplete description of
"The French Proposal for the Cipher" A5. The cipher consists of three
feedback shift registers; the output stream is the XOR of the MSB of
all three registers. The 19 bit register R1 is given in figure 1 the
LSB after the shift is the XOR of bits 19, 18, 17 and 14). The other
registers are known to be 22 and 23 bits large, and their feedback
functions to consist of only four XORs all together.
Clock control is based on the registers' middle bits (they do not say
exactly which bit in a 22 bit register is "middle"). Each register is
clocked based on its middle bit, inverted if less than two bits are
set. So at least two registers are clocked in each step.
They mention how the keys are loaded, but the order of the bits is not
given. So it seems to me that Ross used the same leaked document from
which COMP128 has been reconstructed.
In his paper "On Fibonacci Keystream Generators", Ross states that the
best known attack on A5 consists of guessing the state of R1 and R2
and work out R3 from the keystream. He writes, "There has been
controversy about the work factor involved in each trial, and at least
one telecom engineer has argued that this is about 2^12 operations
giving a real attack complexity on A5 of 2^52 rather than the 2^40
which one might naively expect."
This known-plaintext attack does not depend on how the keys are loaded
to the registers. To execute the attack, you need to know the
feedback polynomials and the position of the "middle" bits, but the
feasibility of the attack clearly does not depend on a particular
choice of these (still unknown) parameters. So if the French A5 is in
use, it can be broken in 2^52 decryptions.
Assume we have guessed the 40 bits of R1 and R2, and want to find R3,
given the output keystream (that is ciphertext XOR the known
plaintext). We get the MSB of R3 from knowing the MSB of R1 and R2
and the output bit, because the output stream is the XOR of the three
MSBs. So if we can cycle the registers through and get all the 23
bits of R3, we have determined the initial state of R3 and can do test
decryptions to see if the guess of R1 and R2 was right in the first
place. (Note that this works for any feedback polynomial.)
However, not all registers are clocked in every step. Not knowing the
middle bit of R3, in half the cases we don't know if R3 will be
clocked, in the other half we don't know whether R1 or R2 will be
clocked. But if we guess the middle bit correctly, we know which
registers are clocked. Thus the MSBs of R1 and R2 in the next step are
known and we can determine the content of the MSB of R3 from the
output bit. Then, we guess the new middle bit, which determines the
following step and again yields the MSB (bit 22 of the inital
configuration). If we repeat this until we have the complete R3,
guessing 11 bits gets us another 11 bits for free. (Does anyone see a
shortcut there?)
What this means for the security of GSM depends on the GSM protocol.
How much known plaintext does it provide? Are the frame sequence
numbers that are mixed into registers known to evesdroppers (otherwise
they'd have to try ~2^52 decryptions on every frame)?
If the frame sequence numbers are known, the reduced keyspace might
also help to break the encryption. Assuming the 10 zero-bits end up
in R1, you guess the remaining 9 bits and fast-forward the register
according to the random distribution that is given by the position in
the stream you are trying to break (in each step R1 is clocked with
probability 3/4). Then guess R2 and half of R3 as above.
Friday 4/24/98 7:33 AM
John Young
The stuff on linear and non-linear shift register sequences which is now
appearing on jya.com is the 'military-grade' crypto technology.
Semionoff and http://www.jya.com/crack-a5.htm contains material similar
to
what I saw Brian Snow present in schematics of NSA KG units.
The statement by david.loos@eudoramail.com
points to the technology used for military-grade crypto.
The reason NSA regarded the R register, seen at
http://jya.com/whpfiles.htm,
feedback function classified was that it contained a non-linear feedback
function.
I was ORDERED to build UNCLASSIFIED hardware. This is why I stuck the R
register
feedback function in a fast ram.
This similarity between the structure of the nonlinear feedback function
in the
CAVE algorithm seen at
to the feedback function published in my SAND report
reveals "military-strength" technology.
SHIFT REGISTERS.
Words 'shift registers' also caused the Great American Spy Sting bust.
The Cold War is over. And the crypto cat is now about fully out of the
bag.
Let's hope for settlement so that we can all go on to more constructive
tasks.
Later
Monday 5/4/98 7:22 AM
chambers,
Your statement
made at
http://www.jya.com/a5-hack.htm#wgc stuck me as profound.
Reason is that NSA cryptomathematician Scott Judy once told me that I
did not really
understand the principles NSA uses for its crypto algorithm.
Judy proceeded to explain to me that NSA bases its crypto algorithm on
complication,
not mathematics.
Judy apparently did not realize that some years previous NSA employee
Brian Snow showed
us about all of NSA's KG schematics. And their field failure records!
Masanori Fushimi in Random number generation with the recursion x[t] =
x[x-3q]+
x[t-3q],Journal of Applied Mathematics 31 (1990) 105-118 implements a
gfsr
with period 2^521 - l.
http://av.yahoo.com/bin/query?p=gfsr&hc=0&hs=0.
Fushimi's generator is sold by Visual Numerics.
Fushimi's implementation is very well tested. And worked SO WELL that
Visual
Numerics numerical analyst Richard Hanson had TO BREAK IT!
Reason was that the gfsr produces true zeros. This caused simulation
programs
to crash from division by zero.
None of the linear congruential generators produced zeros so the
problem
did
not arise until the gfsr was used.
Hanson ORed in a low-order 1 to fix the problem
Masanori wrote,
Lewis was one of my former ms and phd students.
http://www.friction-free-economy.com/
Cycle lengths of sequences is a fascinating topic.
Let me point you guys to a delightful article on the distribution of
terminal digits of transcendental numbers.
This is a story about Russian-born mathematicians Gregory and
David Chudnowsky.
While the story is fun to read, I think that the Chudnowsky's were
wasting their time.
I think that terminal digits of transcendental numbers have been
proved to be uniformly distributed.
Sobolewski, J. S., and W. H. Payne, Pseudonoise with
Arbitrary Amplitude Distribution: Park II: Hardware
Implementation, IEEE Transactions on Computers, 21
(1972): 346-352.
Sobolewski is another of my former phd students.
Hopefully you guys will read judge Santiago Campos' 56 page
MEMORANDUM OPINION AND ORDER on the Payne and Morales lawsuit
on jya.com within several days.
I made a copy and gave it to Sobolewski on Sunday afternoon.
I want Sobolewski's opinion on what Morales and I should do.
Soblewski lives about two miles from us.
Sobloweski is an administrator [vp of computing at university
of new mexico] and knows how administrators think.
Let's hope this UNFORTUNATE mess involving shift register sequences
gets settled.
But let's not forget our sense of humors despite the about .5 million
dead Iranians.
Hopefully the system will take care of the guys that did that did the
Iranians.
Masanori wrote,
Jim Durham, my seismic data authenticator project leader, retired from
Sandia.
Durham gave me a number of tech reports upon his retirement.
One was authored by Robert TITSWORTHE of jpl.
TITSWORTHE changed his name!
Later
> Does anyone see a shortcut there?
Last time I looked at it carefully I concluded that you only
need to guess the clock inout bit half the time, so you need
about 5 bit guesses giving an overall complexity of 2^45. I
could be wrong though - it's notorious that you only get the
real complexity of an attack when you implement and test it.
Jovan Golic showed that you can get a 2^40 attack with a
little more work, and you can work back from a reconstructed
state to get Kc. This paper is worth studying; it's in the
proceedings of Eurocrypt 97 (LNCS v 1233) pp 239-255 and
entitled `Cryptanalysis of Alleged A5 Stream Cipher'
Ross
Ross Anderson writes:
>> Does anyone see a shortcut there?
I implemented this kind of attack about a year
ago, and you're right, the complexity is about
2^44 (measured).
Greg.
We would be grateful for assistance in obtaining copies of the
following papers, particularly the first:
S J Shepherd, "Cryptanalysis of the GSM A5 Cipher Algorithm",
S J Shepherd, "An Approach to the Cryptanalysis of Mobile
S J Shepherd, "Public Key Stream Ciphers", IEE Colloquium on
These are listed on Dr Shepherd's bio at:
>about chaining of multiple LFSR's (A5 uses three), (Ross, please
>correct me) - and Bruce (or someone else) has seen that Ross's attack
>applies to A5. Note that there are several versions of A5, some
>telco's have phones which use A5/7 - these latter versions tend to be
>even weaker than A5/2! It's worth noting that AP 16.5, to my knowledge
>is talking about the proposed (untested) reconstruction of A5, and not
>a confirmed implementation.
Message-ID: <199805051757.KAA23788@modmult.starium.com>
To: Cypherpunks Lite
J Orlin Grabbe
John Gilmore
The A5 algorithm uses a three level, non-linear feedback shift
register arrangement, designed to be sufficiently complex to resist
attack.
http://www.semionoff.com/cellular/hacking/phreaking/
: A11 A1 A5 AND
A1 0= A9 0= AND XOR
A6 A10 XOR XOR ;
http://caq.com/CAQ/caq63/caq63madsen.html
bill
Message-ID: <354DC8CA.5D34@nmol.com>
Date: Mon, 04 May 1998 07:55:22 -0600
From: bill payne <billp@nmol.com>
To: jy@jya.com, masanori fushimi
The advantages are a lack of mathematical structure which might
provide an entry for the
cryptanalyst, and a huge choice of possibilities; the disadvantages
are that there are no
guarantees on anything, and as is well known there is a risk of
getting a very short period.
Lewis and Payne [16] introduced an apparely different type of
generator,
the generalized feed back shift register (GFSR), by which numbers are
formed by
phase-shifted elements along a M-sequence based on a primitive
trinomial 1 +
z^q + z^p.
The Mountains of pi by Richard Preston, v68 The New Yorker,
March 2, 1992 p 36(21).
Sobolewski, J. S., and W. H. Payne, Pseudonoise with
Arbitrary Amplitude Distribution: Part I: Theory,
IEEE Transactions On Computers, 21 (1972): 337-345.
The GFSR sequence as well as the Tausworthe sequence can be
constructed using any M-sequence whether the characteristic
polynomial
is trinomial or not;...
guys
To: ukcrypto@maillist.ox.ac.uk
CC: cryptography@c2.net, Ross.Anderson@cl.cam.ac.uk
Subject: Re: More on A5 strength
In-reply-to: Your message of "Thu, 23 Apr 1998 15:47:00 +0200." <m0ySMLJ-0003b8C@ulf.mali.sub.org>
Date: Fri, 24 Apr 1998 12:31:55 +0100
From: Ross Anderson <Ross.Anderson@cl.cam.ac.uk>
Message-ID: <E0ySghy-0002Nc-00@heaton.cl.cam.ac.uk>
Message-ID: <199804250312.NAA06926@avalon.qualcomm.com>
To: ukcrypto@maillist.ox.ac.uk
CC: cryptography@c2.net, Ross.Anderson@cl.cam.ac.uk
Subject: Re: More on A5 strength
In-reply-to: Your message of Fri, 24 Apr 1998 12:31:55 +0100. <E0ySghy-0002Nc-00@heaton.cl.cam.ac.uk>
Date: Sat, 25 Apr 1998 13:12:45 +1000
From: Greg Rose <ggr@qualcomm.com>
>
>Last time I looked at it carefully I concluded that you only
>need to guess the clock inout bit half the time, so you need
>about 5 bit guesses giving an overall complexity of 2^45. I
>could be wrong though - it's notorious that you only get the
>real complexity of an attack when you implement and test it.
Message-ID: <199804261242.IAA30483@camel7.mindspring.com>
Date: Sun, 26 Apr 1998 08:41:28 -0400
To: cypherpunks@toad.com
From: John Young <jya@pipeline.com>
Subject: GSM A5 Papers
IEE Colloquium on Security and Cryptography Applications to
Radio Systems, Digest No. 1994/141, Savoy Place, London, 3
June 1994, (COMMERCIAL-IN-CONFIDENCE).
Stream Ciphers", IEE Colloquium on Security and Cryptography
Applications to Radio Systems, Digest No. 1994/141, Savoy
Place, London, 3 June 1994, (COMMERCIAL-IN-CONFIDENCE).
Security and Cryptography Applications to Radio Systems,
Digest No. 1994/141, pp 10/1-10/7, Savoy Place, London, 3 June
1994.
http://vader.brad.ac.uk/finance/SJShepherd.html
