LETTERS

Ada 95

Dear DDJ,

In October 1993, DDJ featured comparisons of various OOP languages. You did a great service by leveling the playing field and demonstrating how a specific problem could be coded and solved in each of the selected languages.

I realize that at the time of your article, the updated Ada standard was not yet available. However, as of February 15, 1995, the Ada 95 language has become an official ISO, ANSI, and FIPS standard. Given that Ada 95 may in fact be the first internationally standardized OOPL, I thought I would contribute an Ada 95 solution to the original DDJ challenge.

Example 1 uses a heterogeneous, linked list of objects that can be dynamically dispatched (through the polymorphic Print routine) depending on the derivation of the abstract type called Item.

The freely available GNU GNAT Ada 95 compiler (available from ftp:cs.nyu.edu in the /pub/gnat directory) was used to compile this code. Besides the OO features, Ada 95 also introduces improvements in exception handling, generic programming, memory management, tasking, and programming-in-the-large.

Paul Pukite

Minneapolis, Minnesota

Stepanov and STL

Dear DDJ,

What I would have given to have had Al Stevens' interview with Alexander Stepanov (DDJ, March 1995) before I attended PLoP '94 last August. Object versus generic. What a great pattern. But will the name "generic" stand? I don't believe so. The concept is too powerful. It also has too much history to be called "generic" for long. Frankly, I'm amazed it has lasted this long.

As a nonprogrammer visiting PLoP '94, I went seeking patterns as a function of Natural Structure--as Natural Phenomenon--the way patterns occur in reasoning styles, which I have studied for 20 years. Programmers at PLoP, it seemed to me, saw patterns as being invented, not discovered. It has yet to occur to the community that they are to be studied as phenomena, the way gravity and electro-dynamics were studied.

Objectivity, as a style of reasoning, has been studied for millennia. And so has its complement: subjectivity. The excitement and recognition being showered on Stepanov and Lee is well deserved. For within the realm of language as object they have clearly differentiated the realm of language as subject. STL-style programming, I predict, if it hasn't already happened by the time you receive this letter, will be called "Subject-Oriented Programming." Stepanov is right. His generic programming is going to launch a virtual tidal wave of scientific study and understanding of language and its structures.

What will happen? If my observations at PLoP are right, I predict the programming community will rediscover both science and history. Pattern programming is what the authors of the five books of Moses were doing in Egypt, while the Chinese authors were writing The Book of Changes and The Book of the Way.

Stepanov and Lee have opened a new struggle: Within the science of language, there is a complementary relation between object and subject. As that mystery unfolds, programmers will surely turn to Oriental history, where complementary styles in structure were studied in great detail. We will all be amazed to learn just how much our ancestors knew about such subtle phenomena as they occur in nature.

Dan Palanza

palanza@delphi.com

Image Authentication

Steve Walton's article "Image Authentication for a Slippery New Age" (DDJ, April 1995) poses an interesting question: how to prove that a digitized image has not been tampered with. Unfortunately, his proposed answer is not secure.

A quick review of his method: Walton proposes combining secret, user-generated keys with checksums of an image. He suggests using the keys as seeds to a pseudo-random number generator, spreading checksum bits around the image in the low-order bits of selected pixels.

What would an attack on this system look like? To know that an image has arrived from Walton without alteration, we must have communicated keys in advance using some trusted channel. In practice, unless Walton and his partners want to spend all their time generating, transmitting, and safeguarding new keys for every image exchanged, they will end up reusing keys. When they do, the system becomes vulnerable to a chosen-plaintext attack.

Assume that an enemy has become familiar with the general method (by reading the source in DDJ). The problem then becomes recovering the actual keys. In a chosen-plaintext attack, we assume the enemy can actually slip images into the communication stream, have Walton seal them, and compare the before and after data. The enemy should choose any two images with the property that the low-order bits of one image are the ones complement of the low-order bits of the other; for example, where image A has a 1 in a low-order bit, image B has a 0 low-order bit in the corresponding pixel.

When the enemy compares images A and B before and after, all pixels where checksum bits are stored can be identified. (You need two bit-complementary images to recover all bits, since comparison of one original image with a sealed version will show only the pixels where the checksum bit is not equal to the original data bit.)

Let's say that checksums are 32 bits, as in the original article. Remember that pixel locations are chosen by a pseudo-random number generator. To recover the original seed for the generator, and thus the key, we need only determine which of the 32 pixel locations represents the initial state of the generator. Pick a pixel position, use it as a seed, and if you can run the generator ahead 31 times without generating a number not in the set of checksum locations--congratulations, you have broken the code. The whole procedure is less than a millisecond of computer time.

Using multiple keys does not materially affect solution time, since each key can be solved for independently. (Walton has designed the system so that bit locations do not overlap between multiple keys; as he must, since if a key overlaps in one location, it will overlap in all subsequent locations.)

Okay, we can break the system with two well-chosen Trojan images. How about the easier and more-practical known-plaintext attack, where an enemy can compare images before and after sealing but cannot necessarily choose the images in advance?

Sure. With only one image before-and-after to work with, the enemy will not recover all the bits in the checksum--probably only half of them. However, he could get lucky and recover the first location in the sequence (after all, there is a 50/50 chance); in which case, he is done. If he isn't lucky, he needs to determine which is the first location he does have, and then run the pseudo-random number generator backward from there to recover the initial state. Knuth shows how to run a linear-congruential generator in reverse. This, too, is just a few milliseconds of compute time. So, some advice: Don't use the checksum-and-key method. A better answer to the problem would be to use the Secure Hash Algorithm to compute a long (160 bits) hash code for an image, and the Digital Signature Algorithm to apply it as a signature. This has two advantages: SHA and DSA are believed to be hard to break, and a public-key scheme such as DSA can provide authentication without having to exchange and safeguard secret keys.

Andrew T. Wilson

andyw@ibeam.intel.com.

Steve responds: Thanks for your letter, Andrew. As near as I can tell, you are absolutely correct except that you assume that the "enemy" has access to before-and-after images. Without these, my statements as to security stand. I'll look up your references on reversing random-number generators (if you can do that, it solves another problem I'm working on) and think a little bit more about what you have said. As far as incorporating DSA, SHA, RSA, and the like, this was the answer I had in mind to one of the "Exercises for the Student" portion, which was left off the published version. It would be a good improvement. However, my purpose in illustrating the techniques of hiding things in noise ("Security by Obscurity") was served.

Network Options

Dear DDJ,

William Stallings' article "Congestion Control in Frame-Relay Networks" (DDJ, March 1995) prompted me to write about our experience in Texas.

There's a saying that if you build a highway, people will drive on it. Texas has adapted this idea to information technology and found that if you build an information infrastructure, people will use it.

According to the Texas Department of Commerce, TEXAS-ONE, a State of Texas- lead proposal, has been awarded $25 million in the Federal Technology Reinvestment Project competition. More than 2800 proposals requesting a total of $8.5 billion were submitted from companies, universities, state and local governments nationwide. The Texas Open Network Enterprise, TEXAS-ONE, will serve small- and medium-sized manufacturers in Texas by providing an electronic-information network like those previously accessed only by large corporations able to afford infrastructure investment. TEXAS-ONE is a partnership led by the Texas Department of Commerce, the Microelectronics and Computer Technology System, the Texas Department of Information Resources, the Texas Innovation Network System, NASA's Mid-Continent Technology Transfer Center, and the University of Texas at El Paso.

TEXAS-ONE is a model of what can and needs to be accomplished as we grapple with the design and implementation of a national information superhighway.

Jimmy A. Castro

Austin, Texas

Setting the Revolution Record Straight

Dear DDJ,

Regarding Jonathan Erickson's "Editorial" in the January 1995 issue of DDJ: Actually, it was the Mark-8 on the cover of the July 1974 issue of Radio-Electronics that ushered in the personal-computer revolution. The Altair on the cover of Popular Electronics didn't arrive for another six months. By then, the revolution was already underway.

Jon Titus

Milford, Massachusetts

Flash File Systems

Dear DDJ,

Peter Torelli's article, "The Microsoft Flash File System" (DDJ, February 1995) concluded: "If standards begin to solidify and enough resources are devoted to the development of other operating-system FFS drivers, flash cards could become a dominant form of data exchange for computer users."

The fact is that flash cards already are becoming a popular form of data exchange for computer users because there already is a dominant cross-platform standard for flash cards called the "PC Card ATA Standard." It was developed by PCMCIA. Many large vendors, including Hewlett-Packard, IBM, Casio, Fujitsu, Motorola, 3M, and Verbatim, market ATA cards because they are "plug and play" in thousands of computers, PDAs, handheld data-collection terminals, and cellular phones.

Incompatibilities between various FFS and FTL products have been resolved by companies producing flash cards that meet the PC Card ATA Standard.

Nelson Chan

Santa Clara, California

Running Light

Dear DDJ,

I do not always have time to read the whole DDJ, but I always take time to read Michael Swaine's "Programming Paradigms," as well as his (e)musings on the last page--"Swaine's Flames." Mostly I find his reflections well founded, although I may not always agree. However, when we disagree on such a fundamental issue as the meaning of "running light," I have to express my concern. "Light" in this respect should not primarily be associated with efficient programming related to bytes or machine cycles as Michael states in "Programming Paradigms" (DDJ, March 1995), but rather to a minimalistic approach to functionality. Maybe the idea behind Occam's razor best expresses my thoughts, with featuritis as its antithesis. A small, fast-running program is very often--but not always--the result.

Torbjorn Sund

torbjorn.sund@tf.telenor.no

Example 1: Ada 95.
package PList is  -- A printable list of heterogeneous items
   type Item is abstract tagged null record;
   procedure Print (This : Item) is abstract;
   type Element is access Item'Class;
   type List is private;
   function New_List return List;
   procedure Append (To_List   : in out List;
                     This_Item : in     Element);
   procedure Print (This : in List);
private
   type Node;
   type Pointer is access Node;
   type Node is record
      Contents : Element;
      Next     : Pointer;
   end record;
   type List is record
      First, Last : Pointer;
   end record;
end PList;
package body PList is  -- The implementation of printable list
   function New_List return List is
   begin
      return (List'(First => null, Last => null));
   end New_List;
   procedure Append (To_List   : in out List;
                     This_Item : in     Element) is
      New_Node : Pointer := new Node'(Contents => This_Item, Next => null);
   begin
      if To_List.First = null then
         To_List.First := New_Node;
         To_List.Last := New_Node;
      else
         To_List.Last.Next := New_Node;
         To_List.Last := New_Node;
      end if;
   end Append;
   procedure Print (This : in List) is
      Current : Pointer := This.First;
   begin
      while Current /= null loop
         Print (Current.Contents.all);
         Current := Current.Next;
      end loop;
   end Print;
end PList;
with PList, Text_IO;
procedure Test is  -- The main program
   Object_List : PList.List := PList.New_List;
   type Number is new PList.Item with record
      Value : Integer := 0;
   end record;
   procedure Print (This : Number);
   type Point is new PList.Item with record
      X, Y : Integer := 0;
   end record;
   procedure Print (This : Point);
   N1 : aliased Number := (Value => 10);
   N2 : aliased Number := (Value => 20);
   P1 : aliased Point  := (X => 2, Y => 3);
   P2 : aliased Point  := (X => 4, Y => 5);
   procedure Print (This : Number) is
   begin
      Text_IO.Put_Line ("Num:" & Integer'Image(This.Value));
   end Print;
   procedure Print (This : Point) is
   begin
      Text_IO.Put_Line ("Pt:" & Integer'Image(This.X) & Integer'Image(This.Y));
   end Print;
begin  -- Add Number and Point items to list and then print
   PList.Append (To_List => Object_List, This_Item => N1'Access); -- by name
   PList.Append (Object_List, N2'Access); -- or by position
   PList.Append (Object_List, P1'Access);
   PList.Append (Object_List, P2'Access);
   PList.Print (Object_List);
end Test;

Copyright © 1995, Dr. Dobb's Journal