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,
Editor,
Just a quick comment on Dan Saks' column on Classes vs. Namespaces in the July 1998 issue — he mentions there aren't good references on how to use namespaces. Sure there are, only historically it's been called "named common!"
Mike Lally
North Billerica, MAUh, I think namespaces in C++ have a bit more structure. — pjp
Dear CUJ:
I read Warren Ward's article on stream encryption with great interest. I have used various encryption algorithms before and always wanted a simple "good enough" version. As there was no email address provided with the article, I have to use the letters forum. (Please encourage writers to include contact info.)
As a hardware (and software) engineer, I have used countless shift registers. However, Mr. Ward's code does not seem to implement a real shift register. (In the following pseudo code, LSB/MSB means Least/Most significant bit.) From Mr. Ward's code:
if LSB==1 then LSR = (LSR ^ (mask >>1))| MSB { LSR is not shifted! } else LSR = (LSR >>1) & ~MSBThis is different from the random (noise) generators I have used:
if LSB==0 then LSR = (LSR>>1) ^ mask else LSR = (LSR>>1)Mr. Ward's code only shifts the data if the LSB is zero. The second is from hardware and software applications that I have obtained from several sources. Note, the mask must include the MSB bit to cause the feedback of the LSB to the MSB (optimizes out separate AND/OR feedback.)
The second example also does not have the "all zero" problem. The feedback is inverted; a zero will feedback ones. Also, bit length is set by selecting the highest bit in the mask.
Maybe the code given is not what he intended:
m_LFSR_A = ( (m_LFSR_A ^ ( m_Mask_A >> 1 )) | m_Rot1_A );Perhaps it should have been:
m_LFSR_A = ( (( m_LFSR_A ^ m_Mask_A ) >> 1 )) | m_Rot1_A );This code is repeated for all three shift registers.
I'm curious as to Mr. Ward's response on the above variations. Thanks to Mr. Ward and CUJ for providing great information in your publication (of the dozen or so magazines I get a month, this is the only one I pay for :-)
Best regards,
Scott Henion
shenion@shdesigns.atl.ga.usWarren Ward replies:
Dear Scott,
The folks at CUJ forwarded your comments to me, and I'd like to respond.
(1) "only shifts the data if the LSB is zero"
I can understand how the implementation of the shift registers in the article may look a little odd to you. When I first found the linear feedback shift register (LFSR) technique ("Pseudo-Random Sequence Generator for 32-Bit CPU's," Bruce Schneier, Dr. Dobb's Journal, February 1992), I could see how the physical shift register was modeled in code. This was very similar to the way that you showed shift registers in your letter.
For example, to implement an LFSR, you need to grab each of the bits equivalent to one bits in the mask. They must then be XORed with each other to get the new bit to feed into the left side of the shift register (the MSB) when the shift register is clocked. In a conventional CPU, there is no one-step way to perform this XOR operation. Each one bit in the mask must be XORed in a separate step, and the results accumulated until all the mask bits have been processed. An example of that approach is as follows:
int Cryptor::Get_Random_Bit() { // LFSR1 is an unsigned long // integer, property of the Cryptor class. // The LFSR mask (tap sequence) // covers these bits: // 32, 7, 5, 3, 2, 1 LFSR1 = ( ( ( (LFSR1 >> 31) // Get 32nd bit ^(LFSR1 >> 6) // XOR it with 7th bit ^(LFSR1 >> 5) // XOR with 6th bit ^(LFSR1 >> 1) // XOR with 2nd bit ) && ( 0x00000001 ) // Retain only the 1st bit ) << 31 // Move result to the 32nd bit position ) | ( LFSR1 >> 1 ); // OR the new MSB // with the register // shifted right one bit. // Return 1st bit return ( LFSR1 & 0x00000001 ); }This code works just like a conventional hardware shift register in what the textbooks call the Fibonacci configuration. The only problem with implementing this approach in code is the large number of operations it uses to get a single bit: seven shifts, five XORs, an AND, and an OR.
I looked for approaches that were more efficient when developing this encryption technique for our internal use. Some years after reading the above article, I ran across a modification to the feedback scheme that would remove most of the shift operations and allow all the XOR operations to occur in a single step. The code no longer models the classic Fibonacci configuration for the shift registers, but rather a Galois configuration.
There's a good discussion of both techniques in Schneier's Applied Cryptography (2nd edition, p. 369 ff.). I'll quote briefly from his description of the Galois configuration shift register: "Instead of using the bits in the tap sequence to generate the new left-most bit, each bit in the tap sequence is XORed with the output of the generator and replaced; then the output of the generator becomes the new left-most bit." This form of operation is quite different from the standard hardware or software shift register, and that is why the code in the article looks different from the examples you quoted. It is quite a bit faster on a conventional CPU, though, and met my goals of efficiency with decent cryptographic qualities.
(2) "the all-zero problem"
As far as I can tell, all LFSRs have what you called "the all zero problem" — not really a problem, just the nature of the the beast. I have seen several set up with inverted logic to the code I used, but the developers warn of "the all ones problem:" if the LFSR is loaded with ones, it will never produce a zero bit for output. For example, check the technical notes at Altera for the following warning regarding their hardware LFSR: "A state consisting of only ones is illegal; if the counter contains all ones, it cannot leave that state unless the counter is cleared or another value is loaded." See:
http://www.altera.com/html/programs/amppmf/linear.html.Another way to put it is that LFSR's have one less valid state than the total number of states allowed by the size of the LFSR. For example, a four-bit LFSR has 2^4 (16) states. But only (2^4 - 1) of them are valid: either the all-zeroes or all-ones state will be invalid, depending on the design of the LFSR. This rule of thumb does not generally apply to other types of shift registers, but it does to the LFSRs I've seen.
(3) "maybe the code given is not what he intended"
This was an excellent point. After I looked at your letter, I double-checked my sources, and contacted Bruce Schneier for additional information. Here's a very shortened version of my questions and his response:
Warren Ward: The line in question from my copy of the first edition (page 356 of the printing with "10 9 8 7 6 5 4" on the details page) is:
ShiftRegister = ( ShiftRegister ^ ( mask >> 1 ) ) | 0x80000000;The second line of code on page 379 of the second edition reads:
ShiftRegister = ( ( ShiftRegister ^ mask >> 1 ) | ...I wonder if you could clarify this for me and let me know whether you would interpret the line as:
(A) ShiftRegister = (ShiftRegister ^ (mask >> 1)) ...or:
(B) ShiftRegister = ((ShiftRegister ^ mask) >> 1) ...Bruce Schnier: You're right. B is correct.
In brief, both the first and the second editions of Applied Cryptography had errors (different ones) in this statement, and the book's most recent errata sheet also had an error describing the error. As you can see by Bruce's reply, your interpretation is correct. I will be contacting C/C++ Users Journal with a correction of the code in my article [We have now updated our ftp site with Warren Ward's corrected version — mb].
I hope I speak for Mr. Schneier as well as for myself in thanking you very much for your careful review of the code, leading to the cleanup of this statement. It's a little disconcerting to find a hole in a security feature, but far better to find and correct it than to let it stand. I suspect that, for our internal company use, even the flawed code is adequate for the purposes we put it to. But for other readers needing encryption, the corrections will be very welcome.
Yours sincerely,
Warren Ward
VP Research and Development
Winterforce Laboratories
Copyright (c) 1998 by Warren Ward. All rights reserved.
Dear CUJ,
I noticed two problems in your September letters column. Chuck Allison made no comment on JP's incorrect coding of the singleton pattern. The relevant code was:
class UtConvertTime { public: static UtConvertTime * UtTimeInstance(); private: UtConvertTime(); static UtConvertTime * itsInstance; };First note that the dynamic instance of UtConvertTime is never cleaned up (I also note that UtTimeInstance relies on zero initialisation of class statics). Second the writer (in excellent company) has forgotten to declare a private copy constructor. Unfortunately the grammar of C++ allows (I believe it requires, despite the probable undefined behaviour) compilation of:
UtConvertTime utc = utc;which is one reason that I strongly exhort programmers to use function-style initialisation and not the C assignment style. In this case, as you can create an instance, it can be copied even though you clearly do not intend that. It seems to me that the following is a better implementation of the singleton pattern in this instance:
class altUTC { public: static & altUTC (){ static altUTC instance; return instance; } // public functionality private: altUTC(); altUTC(altUTC const &); // data };Note that if you never want a class instantiated you only need to declare a private copy constructor but if you want to restrict instantiation to the scope of the class and its friends you must declare a private copy constructor as well as at least one other. Note that simply declaring a private destructor may not meet all your requirements.
The second problem is in the letter from Sol Foster. I largely agree with his sentiments, which is why I was surprised to see him pass an auto_ptr<> by value. Because of the ownership semantics of auto_ptr<> it should hardly ever be passed by value as the results will almost always be catastrophic. Plain pointers are passed by value, but auto_ptr<> should be passed by reference (well, I guess the diehard "pass by pointer" brigade will want to pass a pointer to an auto_ptr<>. :-)
Finally, may I commend you on the excellent standards you are setting and congratulate the readers on having the good sense to subscribe. I am continually baffled by the number of programmers who never read anything to help them improve and keep up to date. I bet you would not go to a doctor who never read a medical journal, so why do people employ programmers who proudly declare that they never need to read books or magazines on programming?
Francis Glassborow
Chair of Association of C & C++ Users
Oxford UKAll opinions are mine and do not represent those of any organisation.
A failure to respond to letters should generally be laid at my door, not the author's. Francis, as usual, supplies valuable information on how best to code in C++. — pjp
In fairness to Chuck, what I asked him to comment on was the appropriateness of the Singleton pattern to the reader's problem, not the quality of the implementation. I think I caught him off-guard. — mb
Marc:
I'm sure it was unintended, but your CUJ September 1998 editorial may mislead some readers on the real (that is, my) history of computing and its usually accepted terminology.
Jacquard's loom inspired Babbage, Hollerith, fairground-organ and player-piano designers with the notion of controlling diverse mechanisms via perforated tapes, cards, rolls, and sheets. But the term "stored program" is usually reserved for the breakthough in digital computing circa the mid 1940s, long before ICs (or indeed any microelectronic devices) were invented. The key element in "stored program" machines, regardless of the underlying storage technology, was that programs and data were stored together in the same (usually binary) format, and that instruction sequences could be modified automatically according to intermediate results and IF/THEN tests.
Babbage and Ada Lovelace dreamed of such flexibility but couldn't implement it successfully with their available cogs! The first practical (i.e., reliable for serious daily use) stored-program computer was Maurice Wilkes' EDSAC I (Cambridge University, UK) derived from the work of Eckert, Mauchly, von Neumann, et al. Note that the earlier Colossus and ENIAC were not true stored-program machines, and that the contemporaneous Ferranti Mk I at Manchester was a mere lab benchtop breadboard with a two-minute MTBF (if you were lucky).
The nested procedural modules you and I love grew out of EDSAC's relocatable subroutines. Yes, relative addressing in 1949! To be honest, programming in machine language was not a load of fun, even when we moved to a simple mnemonic ur-assembler. BTW, Warwick University use a Mac-based EDSAC emulator to show their CS students that there's more to programming than draggin' and droppin' iconic components.
PAX etc.,
Stan Kelly-Bootle
Stan, thanks for writing. No one can bundle corrections and factoids together in a single (binary?) format the way you can. "Stored program" was a poor choice of words on my part, seeing as how it resulted in a namespace collision. What I meant to describe was simply a sequence of instructions. For my purposes, it doesn't matter whether those instructions reside with data, or whether flow of control can be modified as a result of tests. The essential characteristic of my "stored program" is that each instruction executes independently of the others, and is identifiable within its surroundings, say, as a pattern of bits or holes in a piece of paper. I contrast this with a logic circuit composed of NAND gates, flip flops, etc., in which the "program" is expressed purely as interconnections. It may do the same thing as my "stored program," but you can't find anything in the logic circuit resembling an instruction. (There is another interesting can of worms I did not open in my editorial; there are ICs that don't have instruction sets but do have programmable interconnections. Maybe some other time...) — mb
Golly, letters from two of the most erudite (and outspoken) Brits in our field, all in one issue! Once again, I really have to take the heat for this one, though. I caught Marc Briand's lapse when reviewing his editorial, but let it pass. (He was on a roll.) Should have known that Kelly-Bootle wouldn't let it get by. — pjp o