Saturday, February 18, 2006

Why I'm No Good At Cryptography

One of my favorite stories from the World War II era is that of the cracking of the Enigma ciphers.  Individuals such as the Polish mathematician, Marian Rejewski, figured out how the Enigma machine worked to scramble information.  But even after that discovery, it was not simple to figure out how to decipher each message.  That is due to the fact that Nazis changed the key for the cipher every day.  Even knowing how the machine worked, it was necessary to figure out what key had been used, in order to decipher the message.

There are many interesting details to the story, but the main point is that the cryptanalysts working on the problem could not rely only on their math skills.  A certain amount of intuition was necessary.  For example, the keys were supposed to be combinations of letters that were chosen at random.  But people being what they are, it was common for non-random factors to intervene.  One such departure from randomness occurred when the Enigma machine operation would spontaneously make up a pseudorandom sctring by typing arbitraty keys.  But since the machine operators fingers generally started from the home positions on the keyboard, the home keys were much more likely to be pressed.  Furthermore, it was common for the operators to alternate keypresses between the fingers of the left and right hands.  

On the Enigma machine, the home keys are asdfghjk.  So an operator who is not careful might choose a-k-a as a key.  Cryptanalysts often used intuition to help them narrow down the list of possible keys.  Rudimentary computing devices could help, but the intuition of the cryptanalyst often resulted in saving a great amount of time in the process.  

Now that computers have become much more advanced, it might seem that there would be no place for intuition.  Just set up the computer to do a brute-force attack, trying every possible key in order to crack the cipher.   But that turns out to be wrong.  A good illustration of this comes from the story of the Chinese mathematician, Xiaoyun Wang.  She has been working on cracking the MD5 and SHA-1 hash functions.  From an article posted on MAA Online, Cracking the Code, by Keith Devlin:
Wang's approach was to input to the algorithm two strings that differ by just a few bits and look closely at what happens to them, step-by- step, as the algorithm operates on them. This led her to develop a "feel" for the kinds of strings that will result in a collision, allowing her to gradually narrow down the possibilities, resulting eventually in her developing a procedure to generate a collision. Others working in the field remark that her ability to intuit which of the many possible paths to follow, coupled with her tenacity, is remarkable. Commenting to the magazine New Scientist, which covered the story in its 17 December, 2005 issue, Charanjit Jutia, a cryptographer at IBM's Watson Research Center in Yorktown Heights, New York, described the challenge of cracking a hash function like SHA-1 as being "like a giant puzzle." Referring to Wang, he added, "Most people get tired and give up. She did not"
I don't want to spur a mass panic, by starting a rumor that SHA-1 has been cracked.  I know full well, what pandemonium would break out if that turned out to be the case.  So, I will clarify that, so far, Wang has only reduced the number of steps required to guess the key.  It had been thought that 2^80 steps were needed.  Wang found some shortcuts that got that down to 2^63 steps.  So SHA-1 still works to effectively obscure private information.  
Following the announcement at Crypto 04, Wang and Yu teamed up with Yiqun Lisa Yin, now an independent security consultant based in Greenwich, Connecticut, and started work on the crown jewel of current hash functions, SHA-1. This proved a much harder nut to crack, but to the general dismay (and admiration) of the computer security community, at the annual RSA security conference in San Francisco in February last year, they were able to announce that they had developed an algorithm that could generate two SHA-1 colliding files in just 2^69 steps.

Unlike MD5, Wang and her colleagues have not (yet) cracked SHA-1, they have just produced a method that could crack it in far fewer steps than was previously believed possible. That number 2^69 is still sufficiently high to provide some degree of confidence in the system's security - for now. So too is the even lower number of 2^63 steps that Wang and other collaborators managed to achieve in the months following the February 2005 announcement.
A lot of computing power is still needed to get the key.  Even so, it is evident that successful cryptanalysis gets a boost from intuition.  And that is why I am not good at it: I don't have the right kind of intuition.

(Note: The Rest of the Story/Corpus Callosum has moved. Visit the new site here.)
E-mail a link that points to this post:
Comments (1)

Tuesday, February 14, 2006

Ann Coulter As Metaphor

Peter Westre, of Left in the Heartland, recently asked for some commentary about Ann Coulter, from a clinical perspective.  This is an interesting topic.  In fact, one could write a book about the subject.  

I am not going to write a book, but I will make a few comments.  

First, the requisite disclaimers.  I have never met Ann Coulter, and I cannot actually make a clinical diagnosis pertaining to someone I've never met.  Second, if I had met her in a clinical context, I neither could nor would say anything about it.  Third, the only information I have is what is available on the Internet, and I haven't read all of that.  What I can do, though, is use the public persona of Ann Coulter as a metaphor for the dark side of the Republican Party.  It would be appropriate for me to say that I do not think that Ms. Coulter is at all representative of members of he Republican Party.  Rather, I would say that the Party has been infiltrated and co-opted by mean-spirited persons who have sociopathic characteristics.  Thus, Ms. Coulter can be used as a convenient metaphor to describe this phenomenon.

Ann Coulter has made some remarks that could be taken as evidence that she is a sociopath.  Editor and Publisher picked up on a few in this article.  Max Blumenthal has more on Huffington Post.  Back in 2001, The Washington Monthly put together a decent collection of some of her earlier and more offensive comments.  Indeed, some of these are highly suggestive.
On Rep. Christopher Shays (d-CT) in deciding whether to run against him as a Libertarian candidate: "I really want to hurt him. I want him to feel pain."--- Hartford Courant 6/25/99
The thing is, in order for someone to be a sociopath, they have to actually do some bad things, not just talk about doing bad things.  Of course, I have no idea if Ms. Coulter ever has done bad things.  Probably not; surely the media would pounce on it if she had.  But the fact is, it is not normal for someone to state openly that they want someone else to feel pain.  The fact that she makes such statements openly is not normal.  It is not normal for someone to say openly, even in jest, that a Supreme Court Justice should be poisoned.  While not conclusive, diagnostically, for someone to make such statements does suggest the possibility of some kind of personality disorder.  

Technically, there are four types of personality disorder that might cause a predilection to make such statements.  If one cared to attempt to establish such a diagnosis, in a casual, armchair-musing kind of way, that could be done.  One would first read the general criteria for a personality disorder.  (The list of criteria can be found on Wikipedia, here.)  If the general criteria are met, one then would read the specific criteria for those personality disorders that tend to be associated with people doing bad things.  Those would be the Cluster B personality disorders: Antisocial, Narcissistic, Histrionic, and Borderline.  Antisocial Personality Disorder is the one that is most closely synonymous with sociopathy.

To meet criteria for Antisocial Personality Disorder, the person in question has to have a history of repeatedly doing bad things.  But what about someone who does not actually do those bad things, but does talk about them in public, repeatedly?      

Looking at the question from a clinical perspective, I would wonder about the Narcissistic and Histrionic personality disorders.  Narcissism can be understood as being pathologically self-centered.  Histrionic Personality Disorder can be thought of a being pathologically attention-seeking, especially if done in a theatrical manner.  

Narcissistic persons have a massive failure of empathy, but typically do not go out of their way to cause harm to others.  On the other hand, if they do happen to cause harm to others (say, by accidentally shooting them in the face with a shotgun), it is no big deal.  After all, it is just "collateral damage."

Histrionic persons tend to be so theatrical that they may, perhaps without really meaning to, cause great insult to others.  Like the narcissist, if they do happen to insult someone, they typically feel no shame; they may even take pride in it.  After all, it is "just a joke."

With those points in mind, now, ignore Ms. Coulter.  Instead, consider  the extent to which the Narcissistic and Histrionic personality disorders can be used, collectively, as a metaphor for the dark underside of a perverted political party.  

Here are the formal criteria for the two disorders:
Diagnostic criteria for 301.81 Narcissistic Personality Disorder
(cautionary statement)  

A pervasive pattern of grandiosity (in fantasy or behavior), need for admiration, and lack of empathy, beginning by early adulthood and present in a variety of contexts, as indicated by five (or more) of the following: 

(1) has a grandiose sense of self-importance (e.g., exaggerates achievements and talents, expects to be recognized as superior without commensurate achievements) 

(2) is preoccupied with fantasies of unlimited success, power, brilliance, beauty, or ideal love 

(3) believes that he or she is "special" and unique and can only be understood by, or should associate with, other special or high-status people (or institutions) 

(4) requires excessive admiration 

(5) has a sense of entitlement, i.e., unreasonable expectations of especially favorable treatment or automatic compliance with his or her expectations 

(6) is interpersonally exploitative, i.e., takes advantage of others to achieve his or her own ends 

(7) lacks empathy: is unwilling to recognize or identify with the feelings and needs of others 

(8) is often envious of others or believes that others are envious of him or her 

(9) shows arrogant, haughty behaviors or attitudes

Reprinted with without permission from the Diagnostic and Statistical Manual of Mental Disorders, fourth Edition. Copyright 1994 American Psychiatric Association

Diagnostic criteria for 301.50 Histrionic Personality Disorder
(cautionary statement)  

A pervasive pattern of excessive emotionality and attention seeking, beginning by early adulthood and present in a variety of contexts, as indicated by five (or more) of the following: 

(1) is uncomfortable in situations in which he or she is not the center of attention 

(2) interaction with others is often characterized by inappropriate sexually seductive or provocative behavior 

(3) displays rapidly shifting and shallow expression of emotions 

(4) consistently uses physical appearance to draw attention to self 

(5) has a style of speech that is excessively impressionistic and lacking in detail 

(6) shows self-dramatization, theatricality, and exaggerated expression of emotion 

(7) is suggestible, i.e., easily influenced by others or circumstances 

(8) considers relationships to be more intimate than they actually are

Reprinted with without permission from the Diagnostic and Statistical Manual of Mental Disorders, fourth Edition. Copyright 1994 American Psychiatric Association

Consider the question, of whether there are elements within the Republican Party that reflect these criteria for mental disorders.  Are there frequent instances of the Party have a grandiose sense of self-importance?  Has any member of the Party ever stood on an aircraft carrier, with a large banner proclaiming "Mission Accomplished?"  Do any of them ever seem preoccupied with fantasies of unlimited success, power, brilliance, beauty, or ideal love?  Well, forget the ideal love part, and think about the rest of it.

What about the third criterion for NPD?  Any hint of exclusivity in the statement about the "haves and the have-mores?"
“What an impressive crowd: the haves, and the have-mores. Some people call you the elite. I call you my base.”
I could go through most of these criteria, and find numerous suitable examples for each, but that merely would be feeding the vampire.  

(Note: The Rest of the Story/Corpus Callosum has moved. Visit the new site here.)
E-mail a link that points to this post:
Comments (1)