Monday, June 30, 2008

I am reality pondering reality

Philosophical thought experiments like the Chinese Room can lead to an unnerving conclusion. These experiments argue that an indispensable ingredient of human-like consciousness is semantics. Human thought uses "high-fidelity" representations of reality, not merely symbols. And a mind switches between "raw" (though still contextualized) data and symbols as necessary...while talking, for instance. Being minds, this is natural to us.

If an essential trait of genuine thinking is the affinity of thoughts to reality, then clearly the very capability to think is deeply influenced--informed--by someone's experiences. And if experiences inhabit a strong role as the substances of thoughts, then what the mind does is intimately tied to how reality impinges on it. Thus, whenever a mind thinks, one simplified interpretation is that reality is doing a computation on itself. An analogy is two parts of reality finding each other. Reality co-wrote the concept of tabula rasa.

An alternative statement is that sensations mold neurons but those same neurons perhaps significantly influence future thoughts. This is consistent with the research that has confirmed the benefit of deep and varied education, in the broadest sense, on effective mental function.

Wednesday, June 25, 2008

the Autonomous cipher

The basic outline of a cipher is that it combines a message and a key to produce unreadable text. At some level, then, the key is like a set of instructions that informs the encryption algorithm about what to do with the message. Compare the process to that of assembling an attractive grill. The message is like the parts, the key is like the sheet of directions, and the finished grill is the encrypted message (presuming the directions' language isn't French--"Le grille?...What the hell is that?!"). Why not have the key actually be a set of encryption instructions?

The Autonomous cipher uses this concept. In this cipher, each digit of the key represents two operations (the key "self-directs" the encryption to a large degree, hence the name Autonomous). The operations' instructions assume a "current cipher index" variable, i, of an array of numbers representing the message. For that matter, the message array could be visualized as a long "tape" and i could be visualized as a "read/write head" that shifts position along the tape:
  1. "0" increases by 3 the array value whose index is i and subtracts 3 from i; corresponding operations of the remaining digits will be displayed as pairs
  2. "1" is (3,2)
  3. "2" is (1,2)
  4. "3" is (3,-1)
  5. "4" is (1,-3)
  6. "5" is (2,3)
  7. "6" is (1,-1)
  8. "7" is (3,4)
  9. "8" is (2,-2)
  10. "9" is (1,4)
Bonus points to anyone who noticed the Turing Machine references. The rest of the encryption algorithm is simple (simpler than the Pointed cipher) because all it does is interpret the key.
  1. Convert the message to a numerical representation as an array of numbers. Duh.
  2. Set both i and the reading position of the key (key index) to 0. Perform the following two steps until the resulting value of i is 0.
  3. Use the key index to determine which instruction to execute, then execute it. This means i and the message array are updated accordingly. When i "falls off" either end of the array, merely wrap it around to the other end.
  4. Increment the key index. Wrap around to the start of the key if the end is reached.
  5. Undo the last increment of the key index; it wasn't actually used. Then append this last value of the key index to the end of the message array.
The decryption algorithm is the encryption algorithm in reverse (flip integer signs, change i before modifying the array, etc.). It should be noted that a more helpful visualization of the message array is a circle, because of the wrap-around. Study of the cipher leads to some conclusions.
  • Any given key may not really work for any given plaintext, for two definitions of "not work": 1) the key starts with a sequence like '18' (i + 2 followed by i - 2) and therefore halts before barely encrypting at all, 2) the key consists of instructions that will jump around but never return to 0 in a reasonable time for the message text. The most extreme example of case 2 is a key that starts with '9' (i + 4) then continues in infinite repetitions of '583' (i + 3, i - 2, i - 1). However, all finite keys will repeat eventually, and with enough repetitions all keys must return to 0. When the net effect of a key is to go from 0 to "x" on a message of length "m", there exist a number of repetitions "r" and a multiple of m "n" such that m*n = r*x. (Any multiple of m works for returning to index 0 because it's identical--congruent--to repeatedly moving from 0 to 0, 0 = (0 + m) % m.) Rearranging terms yields m/x = r/n where m and x are constants. One solution among many to this two-variable equation is r = m and n = x. Stated in practical language, no matter what a finite key does and no matter how long the message is, the index will certainly return to 0 after cycling through the entire key a number of times equal to the message length. For long keys and even longer messages, this absolute upper bound on the number of key repetitions is hardly restrictive. In any case, the key may return to 0 much sooner anyway, of course.
  • Although infinite keys may cause problems, any finite key may be arbitrarily extended to produce a longer key, a key that requires more cycles to return to 0. This extension can be accomplished with a couple techniques, but I suppose there are many more possibilities. 1) Replace one or more digit(s) with other digits that have the same net effect. The key thereby will take more iterations to return to 0, as long as none of the "intermediate" steps of the replacement lands on 0. Two '1' or '2' digits (+2 each) can take the place of one '9' digit (+4). A '76' (+4 then -1) can take the place of a '5' (+3). A more complicated replacement is '2' (+2) by '2233' (+2 then +2 then -1 then -1). And each '2' in '2233' can then be replaced by '2233', and so on--but each of these specific replacements only succeed when the value of i before the replacement point, "j", solves none of the equations (j + 4) % arraylength = 0, (j + 3) % arraylength = 0, (j + 2) % arraylength = 0. 2) At some point in the key when i is not 0, i.e not at the start or end, insert another (full) key. By definition, the net effect of the inserted key will be 0. However, as before, the inserted key itself must not incidentally hit 0 as it runs. Assuming the value of i in the enclosing key is "j" at the point before insertion, the inserted key must not ever attain the i index "message length - j" when it runs on its own. For instance, consider two boring keys for a simple message length of 8. Key A is '99' (+4 then +4). It has only one intermediate value, 4. Key B is '2143' (+2 then +2 then -3 then -1). To make B longer by inserting A, A could be inserted before '3' to produce '214993' because one of A's intermediate i values isn't 8 - 1 = 7. A couldn't be inserted before '4' to produce '219943' because (the only) one of its intermediate values is 8 - 4 = 4. The key would end up being '219', one digit smaller than the original! Notice that B could also be inserted into B, '2(2143)143', since B never assigns i the index 8 - 2 = 6.
  • Looking at the list of ten operations, some interrelationships stick out. Five decrease i (03468), five increase i (12579). For each particular change in i, one or two operations perform it. -3 has 0 and 4, -2 has 8, -1 has 3 and 6, +2 has 1 and 2, +3 has 5, +4 has 7 and 9. Complementary pairs of digits that undo each other's effects, and so are by definition keys, are (0 or 4) and 5, (1 or 2) and 8. Complementary triples of digits that have a net effect of 0, and so are by definition keys, are (1 or 2) and (3 or 6) and (3 or 6), (3 or 6) and 8 and 5, (7 or 9) and 8 and 8, (7 or 9) and (0 or 4) and (3 or 6). Remember that order doesn't matter in these keys. '385' is a key so '538' is also a key.
  • The digits of irrational numbers might not be as promising for keys as one would think. pi is not. '3141', one of the possible four-digit keys, is when pi stops. The square root of 2 isn't much better. It stops at '14142', five digits long. '141' having a net effect of +1 is a bit of a show-stopper.
  • A direct crack of a ciphertext, as opposed to indirect methods like brute-force and related-key, begins by looking for clues that help indicate how the ciphertext could have been generated. Metaphorically, the destination ciphertext aids in reconstructing and reversing the encryption journey. But for this cipher, the origin and the destination are the same in one aspect: i's value. The tracing of i hinges on examining the array values; the question is how each final array value differs from what it was before one or more visits from i. Unfortunately, those differences are difficult to compute, because determining the unknown starting value of each array element is precisely the goal of the entire cracking process. Nevertheless, since the starting values are in a known range and each individual increase is in the range 1-3, someone could calculate "ballpark estimates" for the number of "i visits" that possibly resulted in a particular number. The final number of the encrypted message array, an index into the key, also establishes a lower bound for key size. Additionally, a key that repeated before returning to 0 would probably show more telling patterns than a key that didn't. On the other hand, larger keys are more bothersome to work with.
  • Alternative bases for the key digits is a possible variation that would enable a greater quantity of symbolized operations. The operations could become as complex as desired, too, although all operations must be exactly reversible, have inverses. A key in one base could be equivalent (isomorphic) to a key in a second base as long as the set of symbolized operations for the keys was equivalent. The key in the larger base would then be a "short version" of the key in the smaller base, similar to how programmers use hexadecimal.
My Javascript implementation of the Autonomous cipher is part of the blog layout, down at the bottom on the right. In the page source, search for 'autonomouscipher' (one word). If you use it or download it I am not responsible for any awful consequences. I don't advise you to use it for encrypting anything important or unimportant. Legal disclaimer, etc. It's purely for entertainment, educational, and/or edutainment purposes.

Monday, June 23, 2008

the Pointed cipher

Sometimes a leisure-time project can take on a life of its own. In this case, it started with an inspiration I had. I lay much of the blame on my recent reading. What if someone used a cellular automaton (like Game of Life) to encrypt a message? Specifically, Alice would encrypt by encoding a message as an initial configuration of a cellular automaton (like Game of Life) and using the key to determine how board positions map to characters. My motivation was that a message "becoming alive and growing" into unexpected patterns would be quite hard to crack. Imagine if the information content of a message repeatedly folded over onto itself, thereby exhibiting strange chaotic order sensitive to initial conditions. Let a codebreaker try to analyze that.

The problem, as some readers have already guessed, is that the more interesting examples of automata are just not guaranteed to be reversible. A message's encoded information wouldn't always survive the journey. Two different messages could end up with the same outcome, for instance, or a message could merely evaporate after a short number of iterations. The original signal would be so entangled with the encryption-introduced noise that it wouldn't be salvageable...by anyone. Grudgingly, I adopted the restriction that none of my automata rules would include creation or destruction.

This restriction, along with the need to assign axes to the automata cells for the character mapping, just left me with a set of Cartesian coordinates whose movements somehow affected one another. Then I made several observations: 1) per common practice, the number of dimensions can be set arbitrarily; 2) each character can be encoded as the distance along a particular axis for a particular point; 3) interactions among multiple points at once, especially given the number of points needed to encode a message, are often too impractical to calculate.

After experimentation, I've settled on this impractical encryption algorithm. The idea is to divide up a message into tuples or "points", and perform pairwise-defined substitution and transposition on each point for a number of cycles. Track the values of the three parameters that control the operation of the substitution and/or transposition, and increase them (with wrap-around back to the start value) after each cycle. The three parameters are 1) the axes of the two points to manipulate, 2) the index gap between the two points (later points will wrap around the current "block" of points to find a partner and only if the later point wasn't already the partner for that earlier point), 3) the amount to manipulate with. The key has two parts, 1) the positive integer number of cycles "n" and 2) an integer array of axis initializations "d". The dimension "D" is the number of axes, so it's the length of d. D must be one of 2, 3, 5, 6, 10, 15--kudos to anyone who recognizes the definition of this set of numbers before the end of this paragraph. The recommended n is at least 210. However, the size of n must be carefully counterweighted with message length because either one has a strong tendency to drop time-performance (i.e., complexity) like a brick. Analytically speaking, I believe the relationship is O(n), but I only have rough empirical confirmation of that.
  1. Divide the plaintext into blocks of length 30, padding out the last block with blanks if necessary. After each conversion from character to number happens, add the corresponding element from d (plaintext index % dimension works fine). Perform the following steps on each block and concatenate all results. Actually, my implementation modifies the original array in-place, block by block, by passing indexes around.
  2. Start the axis parameter value at 0 (the first axis), the gap at 2*D (pair the current point to the point after the next point), and the amount at 1. Perform the following steps n times.
  3. Loop over the block point by point (this just means increasing the index by D each time), performing the following two steps.
  4. Use the current values of the axis and gap parameters to determine what two indexes to work on. If the referenced values are equal, multiply both values by -1. Otherwise, adjust each referenced value such that the greater increases and the lesser decreases by the value of the amount parameter.
  5. Swap the value of the first axis of the current point with the value of whichever axis of the next point (again, wrapping around the block if necessary) is indicated by the axis parameter.
  6. After looping over the points, adjust the three parameters for the next cycle, starting over at 0 if exceeding maximums. The axis value increases by 1 up to D - 1, the gap value increases by D up to 29 (remember that the gap calculation wraps around the block of points), and the amount value increases by 1 up to 6.
Decryption proceeds by doing everything in reverse. I discovered that perfectly reversing the steps can be subtly tricky.

One characteristic of this cipher that it shares with many other ciphers is its cyclic nature. In earlier tries at an algorithm, when the block size was the length of the text and no transposition step was integrated, specific plaintext lengths and dimension choices would result in characters that only flipped sign, no matter the number of cycles! These were "degenerate" cases when two indexes always paired up with one another; therefore, each gap parameter value was always paired up with the same axis parameter value (although the converse was usually not true--a specific axis parameter might or might not always have been paired up with the same gap parameter).

In a simple example, a message length (padded if necessary) of 32 and a dimension of 4 results in 32/4 = 8 "points" and consequently 8 possible gap values between indexes (0,4...24,28). The gap parameter value cycles through its 8 possibilities as the axis parameter value simultaneously cycles through its 4 possibilities (0,1,2,3), so now a gap of 4 always applies to an axis of 1, a gap of 8 always applies to an axis of 2, etc. The pattern is clear: a "degenerate" case corresponds to when the number of axes is a divisor of the number of possible gaps, for it is those circumstances when the cycle of axis parameter values maps nicely onto the cycle of gap parameter values. What we have here is an application of the fundamental theorem of cyclic groups (the description "maps nicely onto" is an informal way of stating that one cycle or cyclic group is a subgroup of another cycle or cyclic group).

The complication of avoiding these degenerate cases motivated me both to switch to a set block length and to a set collection of dimension choices, where the dimension choices are 1) divisors of the block length and are not 2) divisors of the associated quotient. Put another way, the block length is the least common multiple of the dimension and the block length divided by the dimension. In addition, I preferred smaller block lengths and dimension choices but I also preferred larger amounts of dimension choices. Check the handy Wikipedia table yourself if you like. As previously mentioned, I opted for a block length of 30. The recommended number of cycles, 210, is the least common multiple of the gap parameter possibilities, axis parameter possibilities, and amount parameter possibilities (7).

Key strength is a question I'm not sure how to answer. The key's "n", the number of cycles to run on the set of message points, isn't much of an obstacle to brute-force cracking. If x number of cycles hasn't yielded even a partial message, trying x + 1 cycles is no problem at all! The key's "d", the array of axis initializations, is more promising. Assuming 2000 possible values for an axis (-999 to 1000 inclusive), for a choice of 2 dimensions that would be a mere 2000^2 = 4,000,000. But a choice of 15 dimensions would be 2000^15 = 3.2768 * 10^49 according to my calculator, which is greater than 2^128. In any case, my limited testing indicated that the initialization value for a chosen axis affects a proper subset of message characters, not all--partial keys are useful, but to verify the correctness of the partial key one must have the number of cycles right.

My Javascript implementation of the Pointed cipher is part of the blog layout, down at the bottom on the right. In the page source, search for 'pointedcipher' (one word). If you use it or download it I am not responsible for any awful consequences. I don't advise you to use it for encrypting anything important or unimportant. Legal disclaimer, etc. It's purely for entertainment, educational, and/or edutainment purposes.

Thursday, June 19, 2008

if you want to be taken seriously...

...don't use Comic Sans MS in your email sig. Just don't. I suppose you can use it for your own name to try to give the impression that you're "just a simple, ordinary guy", but under no circumstances use it for your job title or employer. Form reinforces or contradicts content, people. Seeing the words "analyst", "engineer", "senior" in Comic Sans MS font is irrepressibly funny, and I will proceed to mentally point and laugh at your correspondence.

It's also rather disheartening to read the word "services" in Comic Sans MS as part of your employer's name. It really doesn't shore up your customers' confidence that they're buying high-quality expertise...

Thursday, June 05, 2008

when code simplicity is detrimental

I like code simplicity. Code is a composition of pieces or elements, and simplicity refers to a minimal quantity of those. Generally, simplicity confers greater productivity: quicker speed of initial development, safer modifications and later additions, faster understanding for newcomers, easier debugging and profiling, a smaller proportion of time spent on peripheral tasks. I suspect that the insightful application of simplicity is part of the huge skill disparity between exceptional programmers and the rest. An E. F. Schumacher quotation says it better:
Any intelligent fool can make things bigger, more complex, and more violent. It takes a touch of genius—and a lot of courage—to move in the opposite direction.
However, slavish attachment to code simplicity could have counterintuitive results that solve the task harder or wrongly.
  • NIH (Not Invented Here) syndrome. I doubt this term needs any more explanation. Simplicity may be one of its motivations, as in "The solutions that were Not Invented Here are all needlessly intricate for my use case(s); I'll circumvent the learning curve and integration headache by writing for myself just exactly what I need". I admit that occasionally such reasoning is valid, because the outside solutions truly are either too cumbersome or lacking. But NIH is prone to producing code (a custom web framework and/or, horror of horrors, another template language?) that combines breathtaking simplicity with the subtle bugs and limitations that its matured counterparts patched several versions ago.
  • Flattened "lightweight". Obviously, one of the best ways to keep code small and simple is to focus it on a minimal, carefully-selected set of features or capabilities, and maybe also sacrifice unwanted flexibility and reuse. Code written explicitly with that design decision is "lightweight". Lightweight code is often excellent at fulfilling limited requirements in a way that's easy to understand. Unfortunately, when requirements expand, the trickier situations that the lightweight code ignores could abruptly become more important. The good news is that several approaches virtually eliminate the lightweight/heavyweight dilemma: plugin-oriented code for using separate modules as needed, code (component) specialization for connecting up several expert "lightweights" to match a generalized "heavyweight", APIs and standardized cooperation mechanisms for combining code that's similar but has complementary pros and cons.
  • Security. This is one of the inherently trickiest domains of software development. Its experts tend to be tricksy and unconventional, no matter what color of hat they wear. Here more than elsewhere, simple thoughts are typically naive thoughts. Developers who aren't specialists shouldn't be attempting to create "fast, easy, elegant, novel" data protection algorithms. When security matters, simplicity is a much lower priority than proven best practices. To the untrained, inaccurate evaluations of security weaknesses are perilously likely, and the cliché is accurate: a whole security scheme is no stronger than its weakest point.
  • Interoperability. Any successful communication depends on a mutually-understood encoding strategy. For code, whose "intelligence" is drastically limited, deviation from a chosen encoding strategy will result in communication failure in some way, although the failure might not be absolute or fatal, e.g., discarding just the unexpected symbols. Therefore, de-facto and de-jure standards for data encoding are important. But in the majority of situations, the entire depth and breadth of one or more standards really isn't strictly applicable or necessary. Thus, the temptation is to write or reuse code that simply handles the "core subset" of a communication standard. Sometimes this choice is justified, when all the communicators are exhaustively known and under tight control (within an intranet, for instance). Other times, this choice is short-sighted because code that tries to communicate using the standard could try to use the complex parts that were left out for simplicity's sake. XML namespaces and Unicode are two common targets. Fortunately, conforming XML parsers are everywhere and Unicode is built right into programming languages.
  • Scalability. As hardware's twin performance pushes of miniaturization and faster clock frequencies give way to the alternate path of workload parallelization (more cores, more sockets), ignoring code scalability in favor of simplicity becomes a less competitive option. Sure, the individual units of parallelized code are usually pretty simple. Depending on the architecture, the local memory available to each unit might be tiny in modern terms. The complexity arises in the efficient coordination of all the units and in the decomposition of an algorithm into parallel tasks. Another scalability realm is the deployment of code to multiple hosts, especially to high-traffic Web servers. Code that's not written toward this goal has the potential to hinder an even distribution of the user load.