Sense of Wonder | 03-2004 archives

   Nowadays, the typical example to illustrate the inconveniences of the “security through obscurity” method should be the worrisome insecurities of the GSM standard. Designed in 1989, its different security procedures were given the following names:

• A3: authentication algorithm
• A8: key generation algorithm
• COMP128: authentication algorithm widely used for A3 and A8
• A5/1: "strong" over-the-air voice-privacy algorithm
• A5/2: "weak" over-the-air voice-privacy algorithm
• A5/3: add-on stronger over-the-air voice-privacy algorithm .

   Since the beginning, there were problems: the closed design process, the unpublished descriptions of A5/1, A5/2 and COMP128 and the deliberate weakening of the algorithms were a clear indication of the poor quality of the standard.
   A leaked GSM document specifying COMP128 in 1998 started it all, and a corrected implementation of the algorithm came out: a chosen-challenge attack was announced, requiring physical access to the target SIM, although an over-the-air attack could also be carried out. With the SIM internal key and the intercepted random challenge sent by the base station, the attacker can derive the session key used by A5 and successfully decrypt the voice communications.
   With COMP128 broken, A5/1 was the next target: the first cryptanalysis, "Cryptanalysis of alleged A5 stream cipher" based on partial design appeared. But the publication of “A pedagogical implementation of A5/1”, containing an alleged implementation, allowed the first significant cryptanalysis: "Real-time cryptanalysis of A5/1 on a PC". Later, some other efficient attacks have been published:

• "BDD-based cryptanalysis of keystream generators"
• “Cryptanalysis of the A5/1 GSM stream cipher”
• "Another attack on A5/1"

    Bad publicity pressured to release the stronger cipher A5/3, KASUMI, based on MISTY1, which featured an academic design. A number of attacks have been test on both, without noticeable success:

• “On MISTY1 higher order differential cryptanalysis”
• "Strength of MISTY1 without FL Function for Higher Order Differential Attack"
• "Integral cryptanalysis (extended abstract)"
• "Cryptanalysis of reduced-round MISTY"
• “Improved cryptanalysis of MISTY1”
• "Related key attacks on reduced round KASUMI"
• "On the Strength of KASUMI without FL Functions against Higher Order Differential Attack"
  

   With KASUMI, it would seem that the GSM Association has learned from its mistakes: au contraire!. The second version of COMP128, COMP128-2, is unpublished. And even if KASUMI is secure, the protocols haven’t been fixed: the last attack, "Instant Ciphertext-only cryptanalysis of GSM encrypted communication", requests the secret key under the weak A5/2 to later decrypt voice under KASUMI.
   Some of these attacks have been implemented by the following companies (really expensive products!):

• Scandeas
• PGIS
• Shogi
• Securtelecom
• Accelerated Promotions
• DPL-Surveillance-Equipment

Please click on the images to get more information.

Flowers

Anemone

Fishes

Frog

Snakes

Lamprey

Dolphin

Lemur

Cat

Ape

Human-like robots

   Biomimetic robots sure are fun to build and a good investment to get future funding but we should not really need Nature’s pool of ideas: current animal’s shape is based on all previous evolutionary designs so, although adapted to their environments, they’re not the best possible design. Moreover, there are fundamental differences between animals and these robots:

• energy production/consumption is equally distributed over an animal’s body, but in a robot, the production is localized in a specific position.
• information processing is usually distributed over the robot’s body.
• robots do not fix themselves.
• lack of sensors compared to animals.

   A process of optimal shape design must take into consideration factors such as energy consumption, survivability, degrees of freedom, etc... to calculate the best achievable trade-off.

 There are two main approaches: machines that stimulate the brain and specific pharmaceuticals.

 Since direct electrical stimulation of the brain by electrodes has many drawbacks, including the impossibilities to generate non-localized effects of the stimulation and the difficulties to reach profound parts of the brain, a promising technology could be Transcranial Magnetic Stimulation, a tecnique that is used to map the motor cortex and to suppress concrete functions of the brain. It has been shown that when applied to the front part of the brain it speeds up the ability to solve puzzles that require analogical reasoning.

Cogniceuticals

There are already some memory enhancing drugs. For example, Memantine, used to treat Alzheimer’s Disease, is an antagonist that blocks NMDA signalling, improving memory acquisition in these patients. Obviously, it doesn’t work for normal people; for them, it would be possible to use the trial drug Ampalex, from Cortex Pharmaceuticals, that boosts a neurotransmitter, called glutamate, activating its associate protein, the AMPA receptor, which activates the NMDA receptor. Another drug in test, from Nobel prize Eric Kandel's Memory Pharmaceuticals, will boost the messenger molecule cyclic-AMP and CREB levels, which strengthen neural connectivity and consolidate memories, respectively.

Provigil/Modafinil: without addictions or the side effects of amphetamines, this drug keeps individuals awake for two days. Although originally developed to treat sleep apnea/hypopnea syndrome, it has recently been approved to treat excessive sleepiness associated with Shift Work Sleep Disorder. Additionally, it has begun to be used by students all over the world.

  Mass media are quickly echoing that NASA will announce significant findings from Opportunity at a press briefing at 2 PM. EST, Tuesday, March 2, 2004, at NASA Headquarters, Washington. The press note is here. Note that it will be broadcasted live on Internet by NASA TV using Speedera’s content distribution network: let’s see how they manage the flash crowd.

 Meanwhile, Der Spiegel has revealed the secret using the self-justifying argument that German instrumentation was indispensable in the findings, concretely the Mossbauer spectrometer “Mimos II” of physicist Göstar Klingelhöfer at Darmstadt University of Technology:

Erster Verdacht bestätigt

Die "Smoking Gun", der unumstößliche Beweis für die Existenz vergangener Fluten auf dem Mars, sei eine in den Steinen entdeckte Sulfatverbindung, die nur in der Umgebung von Wasser gebildet werden könne. Die Nasa will die Resultate am heutigen Dienstagabend um 20 Uhr deutscher Zeit auf einer Pressekonferenz in Washington vorstellen.
Bereits die ersten Nahaufnahmen der Formation hatten den Verdacht der Planetologen genährt, dass die Gesteine durch Sedimentation, also durch Ablagerung, entstanden sein könnten. Die einzelnen Schichten waren auf den hoch auflösenden Schnappschüssen der Panorama-Kamera von "Opportunity" klar auszumachen. Einen wichtigen Beitrag bei der Entdeckung dürfte das Mößbauer-Spektrometer "Mimos II" des Mainzer Physikers Göstar Klingelhöfer gespielt haben, das für die mineralogische Analyse eisenhaltiger Marsgesteine zuständig ist.

Durchbruch mit deutschen Instrumenten

Schon am 9. Februar hatten deutsche Mitglieder der Rover-Forschertruppe überraschende Ergebnisse ihres APXS-Instrumentes ("Alpha Particle X-Ray Spectrometer") gemeldet. Danach hatten Analysen mit dem Spektrometer in einem hellen Felsen mit dem Namen "Robert E" weitaus höhere Gehalte an Zink und Schwefel ergeben als bei allen bisher untersuchten Marsbrocken. "Dies deutet darauf hin, dass der Stein eine verfestigte, salzhaltige Ablagerung und nicht vulkanischen Ursprungs ist", erklärte ein Mitarbeiter des Max-Plack-Instituts für Chemie, wo das APXS-Spektrometer gebaut wurde.

 For the German-illiterate reader, the extract says that a close-analysis of a stone named “Smoking Gun” has revealed that it could only be formed by sedimentation in an environment with water, demonstrating a non-volcanic origin and featuring high contents of zinc and sulphurs.

 An hour later, BBC tries to remember us that the first “significant indications“ of water on Mars were discovered by Europe’s Mars Express with this press note.

Update:

• Meridiani Planum: "Drenched":"Long ago, parts of Mars were soaked in liquid water, say scientists analyzing data from NASA's Mars rover Opportunity."
• 02-Mar-2004 Press Release Images: Opportunity
• PIA05479: Focus on Guadalupe
• PIA05478: The Texture of El Capitan
• PIA05483: A Trail of Salts

"Les machines un jour pourront résoudre tous les problèmes,
mais jamais aucune d'entre elles ne pourra en poser un !"
Albert Einstein 1879-1955

“Computers are useless. They can only give you answers.”
Pablo Picasso 1881-1973

 Einstein, as with quantum-mechanics, was wrong. Nowadays, computers do not only conceive new problems, they gestate novel and interesting problems.

Who started it all?

 Hao Wang, a pioneer in automated theorem-proving best known for a program that could prove all the theorems of the first five chapters of Russell and Whitehead’s “Principia Mathematica”, followed the next logical step in his research and wrote a program that produced statements in the language of propositional logic in 1959, “Program II”: he reported that the program found 1000 theorems of 14.000 nontrivial statements, and quickly realized that the biggest problem to overcome would be how to determine what were the non-trivial significant statements.

What are non-trivial significant statements?

 This question is a real matter of controversy, rooted in the very heart of the philosophy of mathematics. For example, profound statements may connect previously disjoint parts of mathematics but, for others, the importance of a statement is given by an agreement in the mathematical community to follow a concrete path of research. Arguably, the significance of a particular statement in mathematics is a combination of its historical importance; its abstractness and generality; its beauty and some psychological parameters that trigger the alarm in the brain of the mathematician, among others. But, how should all this be encoded for a computer to discern between interesting and uninteresting conjectures?

Subsequent developments

 In 1970s, Douglas Lenat, Cycorp’s CEO, wrote the Automated Mathematician and Eurisko, programs that rediscovered the Goldbach’s Conjecture and the Unique Factorization Theorem but never made any research conjectures.
 Lately, a reimplementation of the Automated Mathematician by Kenneth Hasse, Cyrano, and Susan Epstein’s Graph Theorist produced no interesting research conjectures.
 In 1985, Fajtlowicz’s Graffiti made interesting conjectures in graph theory collected in Written on the Wall. The next version of Graffiti by Fajtlowicz and DeLaVina, “Forever, Whatever and Dalmatians” and Graffity.PC, created new interesting conjectures collected in Written on the Wall II. Graffiti can also generate conjectures in chemistry, number theory and geometry and has been used in teaching.

How does Graffiti work?

 Given mathematical objects of some type, relations between operations on objects are produced. Then, a first check compares pre-existing conjectures with the new one and keeps those not implied by previous conjectures. The second check tests for the truth of the relation with respect to the stored objects and just keeps those which are true for all the stored objects. To invalidate a resulting false conjecture, the mathematician has to add a counterexample to the objects. As simple as it seems, Graffiti shows that the conjecture-making process does not require thousands of rules, as other may have suggested before: working under the Principle of the Strongest Conjecture, that is, to produce the strongest statement for which no counterexample is known, seems to be the best approach to automated mathematical conjecture making.

Some papers on Graffiti

• On Some History of the Development of Graffiti
• Toward Fully Automated Fragments of Graph Theory

Other programs

 In 1993, a program of Rajiv Bagai rediscovered some theorems in geometry.
 In 1998, Simon Colton presented his program, HR: it produced some interesting conjectures when it was properly directed to search for them.
 Lastly, in 2000 Gilles Caporossi and Pierre Hansen's AutoGraphiX, which uses the Variable Neighborhood Search metaheuristic to find extremal objects with respect to an invariant.

In the Future

 Mathematicians will use automated mathematical conjecture-making tools as now they use computer algebra packages. And if computing power is a constraint, grid computing should provide a powerful platform in which mathematicians will be able to test their conjectures, and, why not, find new ones.