Letters to the editor may be sent via email to cujed@mfi.com, or via the postal service to Letters to the Editor, C/C++ Users Journal, 1601 W. 23rd St., Ste 200, Lawrence, KS 66046-2700.
Dear CUJ,
When using any form of stream cryptography, you never use the same key to encrypt two different chunks of data. Warren Ward's article (September 1998) seems to propose doing just that many times over (in the password file, in columns of a database, persistent object storage, etc). The problem is that knowing just one plaintext — like that I know my own password — would let all the other encrypted texts be broken — since I know my own password, I can derive the stream that got XORed with it and thus XOR that stream with any other ciphertext.
This is a serious flaw. Block encryption using Cipher Block Chaining (CBC) mode does not suffer from this problem. The vast majority of block encryption algorithms use eight-byte blocks (not the 128 or 512 as Warren Ward says).
To Warren Ward's credit, he does admit that you would probably want to spend money on real cryptography if you need real security. Another very good rule of thumb in the world of cryptography is that you never use anything new or that has not been extensively tested and analyzed. Instead of Warren Ward's stream cipher, I would recommend ARC4, available free on the net. ARC4 is not much more complicated then the cipher in the article and it is a tried and tested encryption system.
Michael Heyman
Warren Ward replies:
Dear Michael,
CUJ forwarded your message to me, and I hope I can address some of your points.
(1) "never use the same key to encrypt two different chunks of data"
This is good advice, for the reason you gave. If someone has access to the plaintext and the encrypted text, that person can derive the output from the PRNG and use it to decrypt other items encrypted with the same key and at the same point in the PRNG output stream. Eternal vigilance (with respect to the encrypting keys) is the price of reasonable security through encryption.
For one special application in the article (under the section titled Database Encryption), I did recommend using the identical encryption key for all values in one column, the database key field. This prevents duplicate encrypted database keys from being created from different source database keys, which would harm database integrity for the encrypted table. For example, encrypting the employee ID "RC021" with one key produces "bHm?8," and encrypting the ID "MH749" with a different key produces "bHm?8" as well, harming database integrity.
In other cases, I agree with you and would recommend using varying keys for encryption. For example, in encrypting items in a database record, use one of the record's candidate key fields as the encryption key for the sensitive fields in the record. In a non-database application, where suitable key fodder is less common, set up a method for either varying the LFSR initialization contents or else cycling the LFSRs a varying number of times before using them to encrypt. In the article, I described an application of the first approach for encrypting streamed object contents, where every class has a different key for writing and reading its own encrypted contents.
I might also suggest hashing the key cryptographically (using another secret key) before loading the shift registers, to ensure that shift-register contents are not similar to the plaintext key. This neatly takes care of transforming any key string into a correct-length bit string for initializing the LFSRs, as well as breaking the link between the plaintext version of the key and the actual bits used in the LFSRs.
Unfortunately, each "strengthening" step like this makes the technique more complex, less easy to teach to staff, and less easy to implement correctly (and makes for an article too long to publish in CUJ!). Stacking up a pile of strengthening techniques on the basic algorithm will never catapult it into the big leagues of Blowfish or IDEA, but may give developers the mistaken impression that they have the Maginot line in their back pockets. I would prefer to see the technique in the article understood as a workman's tool, not as (say) an advanced military defense. It has done good work for us, but your comments emphasize how encryption technology can be mis-applied.
(2) "eight-byte blocks"
I checked the article and realized that a typo had slipped by all our proofreading, leaving "bytes" instead of "bits" for "a minimum block of data to work with" in the introductory paragraphs. You are right in that many of the better-known algorithms use a 64-bit block for encryption. The higher numbers I mentioned came from our research for modern, non-licensed encryption algorithms that might suit our purposes in delivering commercial software, such as CA-1.1 (384-bit blocks) or MMB (128-bit blocks).
(3) "never use anything new or that has not been extensively tested and analyzed"
This is certainly true of any method to be used on highly sensitive data, for which I recommend using a commercial encryption library. You are far too kind to me and perhaps unkind to the algorithm, however, in calling it "Warren Ward's stream cipher." It may be reassuring to note that the alternating stop-and-go generator has a fairly respectable cryptological pedigree, with similar generators discussed in technical papers as far back as 1974, and this one presented by C. S. Gunther to EUROCRYPT '87.
Bruce Schneier, in Applied Cryptography (2nd edition,p. 383), says "this generator has a long period and large linear complexity. The authors found a correlation attack against LFSR-1, but it does not substantially weaken the generator." He is much less kind to a variety of other stream-cipher schemes, and that is one reason I selected the alternating stop-and-go generator for use in our software.
(4) "I would recommend ARC4, available free on the net"
I believe ARC4 is Rivest's RC4 encryption algorithm. After it was released anonymously (and apparently without permission) on the Internet a few years back, it has been widely discussed and even used by some for non-commercial purposes. As with many of the well-known, "name brand" encryption algorithms, intellectual property concerns make using it a bit of a challenge for commercial software developers. If I may, I'll quote from Bruce Schneier again ( p. 398), "RSA Data Security, Inc. will almost certainly sue anyone who uses unlicensed RC4 in a commercial product." For most commercial developers, the intellectual property rights retained by RSA are a strong argument against using the algorithm. If the power of RC4 is needed, a licensed library should be used."
One thing that's been emphasized for me in responding to your letter is that cryptology is a vast and complex subject, and the expertise and good judgment to use cryptographic techniques effectively cannot be learned or taught quickly. I hope that the article was clear in scoping this technique for the working developer, who needs something a little more secure than ROT13 or naive XOR encryption, but who wants to avoid the costs or complexity of some of the field's major algorithms and techniques. I think your observations are very much to the point, however, and I want to thank you for taking the time to write.
Yours sincerely,
Warren Ward
VP Research and Development
Winterforce Laboratories
Copyright (c) 1998 by Warren Ward. All rights reserved.
Dear CUJ,
Thanks for the editorial in the September 1998 issue. Regarding the allusion to fun at the end, I don't enjoy it when programming consists too much of just looking things up in an enormous catalog, such as one of components. Never far from my mind is the saying that computers turn mathematicians into clerks, and clerks into mathematicians. I started out to become a mathematician long ago ...
However there are aspects of reality you didn't mention. For one thing, the black boxes of components are often poorly labeled. It can be a wasted creativity, unnecessarily to figure out how components work by guessing, trial, and error. Also, it has been my repeated bitter experience that components may have outright bugs of their own, not to mention your point that they may not do just what is needed.
Thus I strongly prefer components with source code. Even so, in practice they may not work, and one doesn't easily know just what they will do. Ah, the siren call of components: just drop it in.
P.S. I for one want well indexed, complete specifications, with outlines and details. Documents that can be read sequentially in print so that I can flip through the pages and quickly see everything there is to see, slowing down when it's interesting. Then if I just use the function prototypes most of the time, that's great, the details are there when needed. In a nutshell, a complete specification ideally makes it unnecessary to have what it specifies, until time for actual use.
Stuart Ambler
I like your idea of shipping source code and documentation with components (what a novel idea). I guess some might complain that those are just more ways of breaking encapsulation, thus defeating the purpose of components. But when there's a bug in the component, is it still encapsulated? Thanks for writing. — mb
Dear CUJ,
I must remark on Vladimir Batov's article, "Extending the Reference-Counting Pattern," in the September CUJ. Batov's technique is certainly valid in some situations, but it has shortcomings that were not brought out in the article and that may well be important in practice.
Batov contrasts his design with the "usual" implementation, which he claims is to have the handle object point to an intermediate object and have the intermediate object contain both a reference count and pointer to the counted object. This is indeed a common approach, but only for types that don't already hold a reference count of their own. For types that do hold such a reference count, there is no need for a second pointer. In his book, C++ Strategies and Tactics, Rob Murray describes how use of a reference-counting base class and a smart pointer template can make it easy to add reference-counting to any class to which you're allowed to add a base class, and my treatment of the topic in More Effective C++ (which Batov cites) is just a minor modification of Murray's design.
Batov's objection to this design is presumably that it fails to work for types you are unable to modify. That's a reasonable objection, but at least in the presence of inheritance, his cure may be as bad as the disease.
When creating a Handle<T> object, his design creates a new T object by invoking T's default constructor. As I explain in Item 3 of More Effective C++, there are good semantic reasons for avoiding gratuitous default constructors (reasons not addressed by Jim Coplien's (generally very good) Advanced C++, which Batov cites), but here there is a more pernicious problem — Batov's design fails to support inheritance.
Consider the following entirely reasonable client code, where Derived is a class derived from Base:
void f(const handle<Base>& pb); Derived *pd = new Derived; f(pd); // this does NOT call f // with a handle to *pd!Conceptually, f takes a reference-counted pointer to a Base object, and it can modify this object in the usual fashion. In practice, that's not how it behaves. Instead, f takes what amounts to a pointer to a copy of the Base part of whatever's passed to it, and if f modifies anything, it's this copy. Under no conditions can the actual argument be modified. I believe this is counterintuitive even in the absence of inheritance, but in the presence of inheritance (such as in the example above), I have great difficulty imagining a realistic situation where this behavior would correspond to the caller's expectations.
As an aside, Batov encourages pass-by-value for Handle objects, but he concedes that pass-by-reference is sometimes necessary. In fact, pass-by-reference is insufficient. What's really needed is pass-by-reference-to-const as shown in the declaration for f above. That's because temporary Handle objects — such as those returned from functions — can't be bound to reference parameters unless those parameters are references to const. (This was one of several seemingly insignificant language requirements that ultimately shaped auto_ptr into its final not-necessarily-intuitive-but-nevertheless-standardized form.)
Batov's efficiency analysis is incomplete. He correctly notes how his design eliminates one allocation and one indirection in the "usual" approach, but he fails to take into account the cost of creating and destroying the T object stored inside Handle<T>::Counted. Consider this:
// calls 0 Widget constructors auto_ptr<Widget> p1, p2, p3, p4, p5; // calls 5 Widget constructors; // 5 dtors will be called later Handle<Widget> p1, p2, p3, p4, p5;Of course, one of Batov's goals is to make sure that a Handle<T> always points to something, so there is a benefit obtained from these constructions and destructions. Nevertheless, since the first two of his listed three advantages of Handle over conventional implementations of reference counting focus on efficiency, I think it's important to explicitly mention those cases where the Handle design has additional costs.
None of this is to imply that Handle is badly designed. Rather, it is to point out ways in which I believe Batov's presentation could be improved. What I really missed was a summary of the types T for which Handle would be well suited and the environments in which it would best be utilized. Batov suggests that T would most likely be "something more complex than just an integer, like dynamically allocated strings, structures, etc." I must disagree. In my experience, complex structures often lead to inheritance, and I believe Handle's lack of support for inheritance is one of its greatest weaknesses. Rather, I believe Handle is best suited for types where inheritance is unimportant, perhaps for relatively C-like software not taking advantage of C++'s support for inheritance, polymorphism, or dynamic binding.
Finally, I encourage readers to examine Kevin S. Van Horn's truly remarkable smart pointer template at http://www.xmission.com/ \
~ksvhsoft/code/smart_ptrs.html.Van Horn's template allows for the creation of smart pointers that do everything Batov's Handles do, but they can also support many other kinds of behavior, too.
Scott Meyers
Vladimir Batov replies:
Despite the existence of a niche where Handle might be (and definitely is) useful, the two limitations you've rightly pointed out — no support for inheritance and inflexible Data instance construction — make the approach unsuitable for wider audiences. The implementation will likely benefit if I:
1) prohibit Handle(const T*) to save users from themselves as you pointed out.
2) rename Handle to Parcel (Envelope? DataHolder?) to reflect the internal nature of T instance inside the Parcel.
3) implement Handle in the conventional way (:-) using a T* instead of embedded T. (I have to admit it — I gave up my original idea and rolled back to the conventional solution.)
Once I surrended to
Handle<T> handle(new T);instead of just
Handle<T> handle;I could see immediately that it's a small price for T construction flexibility. With a specialized memory allocator (e.g., from the January 1998 issue of CUJ) for Counted instances the memory fragmentation and efficiency are not that much of an issue. It can be misused however as well.
Regards,
Vladimir
I think it is difficult even for experts to look at a piece of code and foresee all its inherent possibilities and limitations. So Scott Meyers' insights here are very much appreciated. Vladimir may be a bit too hard on himself, however. One "niche" in which his approach may be useful is in retrofitting legacy object hierarchies with reference counting semantics. By now, that may not be such a small niche. — mb
Dear CUJ,
While doing a code inspection, I found code similar to this in a person's code:
char string1[6], char string2[6];cin >> string2;
string1 = string2;
When I brought it up to him, we discovered they were working as he intended, copying the contents of string2 to string1. This behavior only works in GNU g++, but not in CodeWarrior (latest version) or Solaris SPARCompiler 4.2 (older version, Oct 96).
In further review of the problem, we wrote and tested the attached program, which also works as it would appear, with integer arrays also! It, however, does not work in gcc, nor does it allow arrays of different sizes to be assigned to each other, giving an appropriate error message.
It appears that the GNU library is treating the core language array as a type of class, and of course does a default member-wise copy of the contents. This is either a bug, a GNU extension, or part of the new standard, but we cannot determine which explanation applies.
Could you please explain what is the correct interpretation of the C++ standard?
Ron Hamann
Array assignment is definitely not part of Standard C or Standard C++. It is either a gcc bug or extension. — pjp
Dear Editor,
A great deal of attention has been focused on the Y2K "bug," but we've got our own potential problem to deal with and I wonder if any of the appropriate standards organizations have been addressing or even contemplating the issue.
The standard library <time.h> components typically (at least in my experience) use a signed long to represent time variables. Since these measure seconds since 00:00:00 1 Jan 1970 and signed longs are commonly 32 bits, this means that the latest time that can be represented this way is 21:14:07 18 Jan 2038. What happens after that depends on the library implementation; some that I have tried will keep on for a little while, others freak out.
Now, I doubt that I will still be practicing in 2038 (if alive at all, I will be 88), but this could certainly become an issue for younger programmers. An obvious temporary fix would be to use an unsigned long for time_t, which would extend the range to sometime in the year 2106. It wouldn't surprise me if some libraries already do this under the hood. That would help, and it might (at least in some cases) even be possible to slip it in in such a manner that older applications could continue to run without change (I know, this is making assumptions about how the code is generated). This could be helpful in cases where original source code has been lost, but I am not optimistic that it would work in all or even most cases.
But this is still a temporary solution. Win/NT (and possibly other modern operating systems that I am not familiar with) uses a 64-bit value (actually, a pair of unsigned 32-bit values) to measure time (for files) in 100 nanosecond intervals starting in the year 1601. At a rough guess, this looks like it would continue to work until around the year 35,000. Still not a permanent solution, but better. I can't think of a permanent solution, but perhaps somebody else has. At the very least, I think this issue needs to be addressed, and the sooner the better. Let's not find ourselves in our own version of the Y2K problem.
Thanks for your support,
Mike Pickhardt
mike_pickhardt@formfree.comI remember when the PDP-8 time threatened to run out in the 1970s, and Digital simply altered the start of the epoch to extend it a few years. It is no longer a problem, since the PDP-8 architecture has faded from the scene. I suspect a similar solution will happen to current architectures over the next few decades. — pjp
Hello,
This is not a major error, but for those of us who have difficulty in finding those "small" errors, I thought I would bring it to your attention. Mr. Becker provides a nice macro for determining the limits of the function pointer list. However, when this macro is actually used the compiler generates a missing token error and complains about a missing parentheses. The macro reads as follows:
#define ARR_SIZE(arr) \ (sizeof(arr)/sizeof((arr)[0])Its use is defined as:
for (i=0; i<ARR_SIZE(func_table); ++i) {.....}When the compiler does its replace, the for statement reads:
for (i=0; i<(sizeof(func_table) /sizeof((func_table[0]); ++i) {.....}Of course it's plainly obvious why the compiler generates the error. The correct macro should read:
#define ARR_SIZE(arr) \ sizeof(arr)/sizeof((arr)[0])This was an excellent article overall and helped me immensely in a project I am currently working on.
Thanks,
Travis M. Cotton
INSpire Insurance Solutions
traviscotton@mindspring.comPete Becker replies:
That final parenthesis must have sneaked away during a cut and paste operation. The code that I wrote compiled just fine, but the parenthesis is missing in the text that I sent to the magazine. So maybe it's the proofreader's fault. Yeah, that's it, the proofreader should have noticed it. Oops, I forgot. I'm the proofreader, too.
Nice mea culpa, Pete, but the proper fix is to add a trailing parenthesis, not to remove the leading one. Otherwise, you risk having the expression in the macro bind improperly when used in a larger expression. — pjp
Dear CUJ,
The October 1998, "We Have Mail" discussed non-constant expressions as case labels in switch statements. Isn't the requirement for constant expressions related to allowing the compiler to generate a jump or a dispatch table, as in Fortran's computed goto?
Tom Steger
steger@tautron.comSort of. Mostly, it's a constraint inherited from the earliest days of C. The C standards committee entertained a proposal or two to relax the requirement, but in the end none prevailed. — pjp o