Start
   Blogaria
   Bored
   bsgen
   c-conf
   Cookies
   cycliclog
   Dialwhatever
   dnspb
   fch
   HammerServer
   jpeginfo
   kalk
   Lectures
   Microproxy
   msc
   Nasapics
   Off The Grid
   Perl course
   PGPkey
   Posters
   SafeEdit
   Simple listserv
   syscheck
   Wallpapers
   xml tools
Karel as an adult



Regarding C++ Lectures

For the attendees of 2012's C++ lectures at the State Univ. of Groningen:

Off the Grid

Off the Grid

In 2011 I gave a lecture on information security at the State University of Groningen (RuG) (If you're interested, there are slides in PDF format). As a little puzzle and food for thought, I introduced Off The Grid encryption. Plus I added a little challenge. Well here it is.

Off The Grid is invented by Steve Gibson (www.grc.com). Read all about it on https://www.grc.com/offthegrid.htm. The idea of this encryption is basically that:

How does OTG work?

OTG encrypts a-z

OTG will only encrypt letters (a-z). It can be arbitrarily adapted for the entire ASCII range (or bigger, UTF-whatever), but let's stick with a-z. That way it's still nicely usable by hand. With this restriction, it doesn't differentiate between uppercase and lowercase.

Latin Squares

You start with a Latin square of 26x26 cells. Each row and column have every character just once (like Sudoku, but there are no sub-squares). To illustrate, here are two mini-squares for the letters a-g. The left one is pretty trivial. The right one also mixes casing ("a" and "A" should be considered equivalently, more on that later).
a b c d e f g
b c d e f g a
c d e f g a b
d e f g a b c
e f g a b c d
f g a b c d e
g a b c d e f
b D C e A G f 
F a b g c d E 
A e D B G F C 
D F G c E b a 
C g a F d E B 
G B e a f c d 
E c F D B A g

What's the algorithm, what's the key?

The key of OTG is (a) the square, (b) the position that you start encrypting (or decrypting). For now let's always take position (0,0), the upper left corner.

So what's the algorithm? For every character a-z in the input, OTG will output 2 characters. Here's how. First a description, then an example to illustrate:

  1. In order to encrypt a character, start scanning from the scan coordinate, which is initially (0,0).
  2. Take turns scanning horizontally and vertically. We'll start horizontally. So the first character must be scanned for in the top most row.
  3. Given the fact that we're working with Latin squares, we are always sure to find the character that we want to encrypt. There's no need to switch to a different row or column.
  4. When scanning horizontally:
    • If the character to encrypt is to the right of the scan position, then output the 2 characters following the input character. Move the scan position just beyond (to the right of) the output characters.
    • If the character to encrypt is to the left of the scan position, then output the 2 characters preceding the input character, but in reverse order (reading right-to-left). Move the scan position to just before (to the left of) the output characters.
    • If the character to encrypt is at the scan position, then act as if it were to the right; i.e.; output the two characters following the input character, and move the scan position to the right of the output characters.
    • When outputting the characters, or moving the scan position, we may need to "wrap around" the row.
    When scanning vertically:
    • If the character to encrypt is below the scan position, then output the 2 characters below the input character. Move the scan position just below the output characters.
    • If the character to encrypt is above the scan position, then output the 2 characters above the input character, but in reverse order (reading bottom-to-top). Move the scan position just above the output characters.
    • If the character to encrypt is at the scan position, then act as if it were below; i.e., output the two characters below the input character, and move the scan position below the output characters.
    • When outputting the characters, or moving the scan position, we may need to "wrap around" the column.

An Example

Here's a random Latin square for a-z. Let's encrypt the message "hello" In the figures below, the scan position is indicated by a little circle. The output characters are in a box.
Encrypting: "h", horizontally.

1. Start at (0,0), the "S".
2. Find "h" horizontally.
3. Output the next 2 characters, "CG".
4. Move scan position to the "W".

So far nothing out of the ordinary.


Encrypting: "e", vertically.

1. Start at (24,0), the "W".
2. Find "e" vertically.
3. Output the next 2 characters, "Fj".
4. Move scan position to the "v".

So far nothing out of the ordinary.


Encrypting: "l", horizontally.

1. Start at (24,18), the "v".
2. Find "l" horizontally.
3. Output the next 2 characters, "SE".
4. Move scan position to the "G".

Note that we had to scan left.
The output is therefore "SE" (right to left).


Encrypting: "l", vertically.

1. Start at (4,18), the "G".
2. Find "l" vertically.
3. Output the next 2 characters, "Os".
4. Move scan position to the "k".

Note that we had to scan up.
Then we found the "l" at the topmost row, so
we had to "wrap around" to the bottom.


Encrypting: "o", horizontally.

1. Start at (4,23), the "k".
2. Find "o" horizontally.
3. Output the next 2 characters, "Nq".
4. Move scan position to the "d".

Note that we had to scan right.
Then we found the "o" at the rightmost column,
so we had to "wrap around" to the leftmost position.


To summarize, the input string hello encrypts into the output string CGFjSEOsNq.

Why are there lower and upper case characters in the square?

OTG was originally invented in order to encrypt the first 6 characters of a site name (e.g., amazon for amazon.com) into a site-password. Hence the upper case characters that sometimes occur. Given the above sample squre, amazon encrypts into BPFdTvXYuCmt. Having the upper case characters makes brute-forcing harder.

For the purpose of this challenge the upper case characters don't really matter (in fact, they might make the solving challenge even easier).

Can OTG decrypt?

Yes. Just apply the algorithm in reverse; it works just fine.

Do you have something to play around with?

Of course. As a download here's the Perl script otg, which implements Off The Grid. It can: If you want to play around with it, follow these simple steps: Here's the "usage" information of the otg script:
This is OTG V1.02 - Off The Grid encryption/decryption made easy!
Read https://www.grc.com/offthegrid.htm for more info.
Copyright (c) Karel Kubat, karel@kubat.nl, http://www.kubat.nl.

Usage:
  otg -g [-a ALPHABET] [-n SWAPS]          print
  otg -l FILE [-a ALPHABET]                print
  otg -l FILE [-a ALPHABET] [-s SEED] [-v] encryptfile FILE
  otg -l FILE [-a ALPHABET] [-s SEED] [-v] encryptstring STRING
    Flag -a: Default ALPHABET is abcdefghijklmnopqrstuvwxyz
    Flag -g: A new grid is generated.
    Flag -l: A grid is loaded from the FILE (use - for stdin)
    Flag -n: Default SWAPS is 100. More is more random.
    Flag -s: Seeds encryption/decryption. Default is to start at (0,0).
    Flag -v: Makes encryption more verbose

Typical usage:
  otg -g print > MySecretGrid.txt
  otg -l MySecretGrid.txt encryptfile Plain.txt > Encrypted.txt
  otg -l MySecretGrid.txt decryptfile Encrypted.txt

The Challenge

The challenge is of course to break OTG. Given a long enough encrypted text, can you reconstruct the square that produced it, and decrypt into a meaningful text? Specifically, the below is an encrypted message. What's the message? (This text is also available as a download. Incase you need a longer blob: here is the same message, repeated 10 times, so you have more encrypted data to play with.)
yI oB IS EU ab Hj ZG ZD Vp jc wb bz rk eD Tc uN pW qp IK rX ev wT vU gy hv jc 
wb bz xF OD Yl Md XM xg Ks oE kf wX tV sr xF jA yr mX PG Wb gK jT iA RQ Je cx 
jD Ic aH tP tf Go EO pT FE nF Aw RG yg Jr Tl JO ad pH ZK Dc eY Gz Ur gh Is rB 
TN Uy bK md jZ Am tQ Wm yN Rt DC oQ cP sC Tz fz vf ph Bw Eh OX cT Yl vR ha yg 
WE dS ad de an by ta eD Yt Ic Qp wn Uq tb PJ Zg fL lT Aw Md zM hP il Zd yo Mt 
lk bN BJ mO rQ xg fb AV sI Jd rN Ry Bt fa Aw RG nv Xt Ix DY Nq Xg hM de zt JT 
ks Rq XM Kd TJ WL Xm dB JU Gz Hv Qv hs Qb Cg yl ps nf vp Su eK iM rd fQ KA ea 
GQ Ic aH tP eK Aj CR CI nM Ch wb Vf pW Ar fH WL qp oB tj mX bT Vf rt jt dg Bz 
th QH nc rY SU dS bf Wb bX kJ Fx sG LU sr Et Rt as QV zN dX vf LQ vH tO fD bk 
Rt NM gk De Kj qJ CQ JX tR WU Tp Nm gK jT tV xU fD Hj ca rX vG mO kT EH nS wt 
sK wd gt Mi kI lq Dx hs tE jR vy Er lO Ct ox Fh zN Tv lk hp TN Uy Li dU sk Eq 
xm gU LU Vh qz YD NF us nS ZJ tj Ux de Cw lQ hp Xc pe zS YK Rq Ji Uv sZ sV ch 
Sl Is aL li hv oN oX Im xF pH JN cT rt Nb rz DW QR ic rz HS xM yu re Jd Sl jR 
yI Oe CZ pL BQ sd Nv IK tf SL Ng Ry Bt Eh vU gy BT jR yI Qb WO HY SO JO bK md 
md kS MT Cw UD zU PA SL Ru lT cO Qe FB Ot IF oQ nc qw nM UM pQ oB sM Sd iM JT 
Hp Ng Qt ap bo DZ oX vj eR Ux kg AV WE Bj Zj HG dN UM as Qw ad eI PJ Wy zU jP 
xM Rq gk zL Qt Cb nc Kw rt Ch hz jB Ro qr FH Hl xZ nZ WO IK nO jB Qe su sl HI 
LM qf mD oN DP Ep xQ Ps PQ Ia zs yl ps Sd cn Rt CD oa zN qP BY VF EY Jk Wl cx 
LM IL bT Ji TU zD pR wT lk oQ Jr xg Ks YF Lf mq Sh CA mc dC AE hp NX Tl Wl Fp 
ER UE Vq vk iM Ax ks tv WE dS Mh tM XU sC YF UM CI oz Oh Lv Wr aW sa SY WM OC 
Cg bw ws Qv Je gs RJ EA uD Bj Zj bH LI ng XY Cs hk wT Qp MU Ri zP rk ea Qu vT 
fD eD PG cY iK SP ih TC hu nZ BO Fz LS KS WI BZ ab Oa Yl bz lS sd pQ oB ML DE 
ji fk gk mt DB Cb OX cT dr iM lY Zk Tr pz Qy Vh Se jD xm QM kr BY VK rX vG Fi 
Oa Nb ok KS WI BZ ab Oa hs Qb WO qR WM TF BD wd nM hs tE Rv Xd ZJ Rt Px ZC hp 
Xc HF PG Ej Wl aM md ZI BT bz zv zp yS oJ ok DL sz Jd kI RT tE Kd of Ft zU Bl 
Mp XN RJ yg vp Zl cu Zf bK md Gy pH lY dJ JN jw CD Kd fY Eq yO pH rt WL zU sd 
pQ cN Iw Gk DC hs Ch mN IY jT tV xU fD Hj ca rX vG mO fJ nd gF tw EF GN yo Nl 
Lr pX hz QL SL tv md cT hs eQ wJ HQ La FL rM Ic lk ao xN ng oX Bo BO Fz QV Vf 
JN DG BT bz zv DL sz Cw sE qs bs JX tR ae za hg OX MO yN gh dn UZ vy Er OD gh 
bK Nm yS ZO rz iM sh BV yH gZ Hy hp Es bx it Uy nM xg Ks tv WE dS Mh jA Uq tb 
iA VQ Vp CT zP HF KI VJ MH Ck hv xE hC ks yw Os wQ LX Wp RS Sh FO Lp by Je cx 
xm wP Wv Ps Hg Jd GE rA FB bW aW Nb aW mI Lb zS cd rB BO nD Hy XD lc pa Mh SF 
FB Uy Li aC fq Nm aU xb Hn YD at vh sg zF ad sG vp WL qp UW bo xM Tk eB sg fa 
dx sL ZU Zd CE tb Hp hs Ch kJ Gu hp Es Uq wb jR TM WQ BH zP OJ vI sM Sd iM JT 
Hp dJ lY Zk zT nW WE dS GP DL mX Mt Od ZU zO rX Mh CH Ex YH dk MX XV vU zP yZ 
EI JO ad de YX Xg bK aR CE Nl dn gU Qh GU gK ba ps XL xF xK KY km UT DY qP LK 
qJ Rq CQ JX tR tC Aw RG vf EU wb Vf al nr pW mA fu kv ad de YX vr jc Dj Od pj 
Vp ZU zO rX hi Cw UD qt RW mu AR xy tj Ux PF rX Mh tb Yl if Td bx Bk Tl hs eQ 
Rp Xd RJ yg Gy mu zO dS Mh tb Yl if Td DU aL Wb pO pz IS Ji yH xU vm VQ sk Uv 
wb Vf JN cT rt WL qp Ps Hg Jd GE rA FB bW ks mt KL bP BQ Oe fu ax qJ vt Cg eV 
BQ Wa Iy mt EK us Ro qr PJ Jd Gu DX zG xg pT Ry LB Oj KL bP Es Wm Xp Rp Od dC 
tV xU Tg DW xj tB PF aE bX Ic nv Wu Xr fk xM fZ dW ax RW rY dW Fu OX Fv RJ ry 
Oi jb gt HC Wl cx GL dC FH Hl xZ ZJ Vc Oa dr Aj CR vL kg zc FM DU Vz iM bX Ic 
nv RQ at LX sh tX DC Jd xF tb IY xP hv CO YF Kd QB zB Wp RS jQ AV av Pz bX dH 
tj hE Ge Kc bo QM Mb Sz Od jp yw QV zN lT CN Xp Vq by Xm hX id kJ yS rX sY RT 
tE Fh az XW sd zU bT bP BQ ZC hV tv WI rY CE zK Ai gh GA nA DU bw PJ dJ lY oQ 
bs kC tf SL vf Ux YF hC rd tM JB kJ zh Ic Qp tM JB GX rz rx Mq Dy tZ ig tf LX 
al mZ lz EQ eK iM sh HW kI oj dV wX ub Rt Lf Dc gd aW CD Nb di VA tj Jd Sl dU 
BO Fz Fh Rq fJ IJ DA Jr gk Pa Kn sd sl HI nH Qv gK jT ZD hj PQ aC sY oj Kj pe 
SX Wx QG uc Se Mu Sc Jr Tl sk zr pH hs Oe CZ uy vG mO fJ QT Td DU aL Wb FN gy 
PE rY yo Gz bT Vf rt Ch hz Om IY xP jQ zc SO xB Qp ry tW su yH Ji yH hs EW JH 
bo xM Tk eB CD xE tN wd EF Fu rb gU pR CT Mg Gu lO DY Fx JX tR br kt HW dx aC 
vG SR jg eD cJ UK ER tf Wx wd tQ cd FN nL kZ IN zG oN oX jc hU li Xs Bl WO Qv 
ta DZ DP gy Cg eV BQ Wa jc tb iA pf Wl tb PJ Ux YF Mo pO pz kt QV Ua Bt ZR QF 
xm xM BE Bl Uz ba ps fk qS cG ER hp sk sP kZ WL ja YH BG Sk AR QL SL lZ GA nA 
UJ rY CE Gz oX eV aB AV zG dw GL pa hi rX vG hj md qw ev pj Jf iJ vG mO yw md 
dh GU eg uM xm gU vp WL iK Bj qb um Rl IL bT Ji Wm pj Xc HF PG Mi dx xg Ks lH 
tQ Bj fC QF xm xM UI qJ dh HK Vp MN YF IN fH ER Je Vy Hw XL lF QM Ik lT xF jA 
yr IS hQ Fz Nz eV BQ Wa Nk nr JN kL nu oQ cP Os Ex QT Jf sr lF FT lJ Ic vU sO 
gK oE Is hp TN Uy ih gU Yt Ic Qp BE DN cj BH Om IY xP jQ Vk BY OJ CE xr ij ft 
PG Nl dn IK Od ap bo ZU md UA MJ jA vh LY PN li Bw XM Lf Uk FS dS pT WB gk bw 
VK nf ba NM Yt Uq ja QT YI mt rz jA yr hE Li sL lv Ck PQ yQ Cn Oa Rp rX sY RT 
tE oa Bw wd ZG ab rU md WI YH MW rX hM YH RJ pX IA Fp WM TF BD wd jU QT Td Uq 
hU li lO Ct GZ tO Cg JH bo xM CQ IJ be DY qP Gm Ix kg wX Zg vy rX Mh FQ YX rw 
TB fi ps XL bM QT XN QN ja nr ZK Fz LS vR UG dJ lY oQ br qB WO Zl uN sy ku Xw 
Yt DU WO IK hS tb PJ PR RJ kj kI RT WI Gk vy rX hi Cw UD Bq yF VJ MH dn Tk Xg 
hi Cw UD Bq bk nc yv FK WI YH ER LS WL UN CQ IJ DA sr kI pz Ko jA yr or Ix DY 
Nq Wn Wr Oa gk ab KI eV aB Xp ta ZU RB jp fJ IJ FC xW Ng cI QC dn kg LK RW rY 
mj LY iA pf Wl et LF wT Qp AV av zP qN sq dL Ic vU JO hM Xw mB PK vW LK La dn 
BE Bl KL hE pR QN wb UM pQ wq Zx MK JB yZ Vp dM zO Xr kf dn za Jf YF vK cm Wm 
zG Ch rk vL eY Mt as Se bs CH Ex YH dk by FN Ru hU jA zl WB Fi cU zN Ae gk VJ 
MW rX vG hj jc Dj Od QN KY pT BF oI Vc LH md UA Qt sg ps Er OD qm xm eV Es Wm 
La YH RJ lB Xm Rq QC Mi xF Mt CI XD Ai Ft dn QM EG gX KA ea Hp QL rz Mi SJ jk 
tE Rq gk Qv Je gs RJ AV HP wd vj VJ dk ZJ KY pT gs PR RJ lB Xm Rq QC Wb iY DZ 
Qt HQ dm Qf GZ LY wm kU IS Jd Sl dU aZ Vk LB UN ps Jo JY wT UT DY qP cX CE EG 
qp sn TJ Nb di pX th uS zO dS be ac bT dJ pW Ic Nv DY EG RQ Je cx Ih pj ER fa 
Aw CS lz Rh de rX ev uS md jc hU li Xs sp cT Ax MW Er QC Mi Aw Md Iy WL Rt oN 
DP OJ IC Jd th NQ nv HW rk jP Yt Ic Qp tM JB WT hu MB yF VJ GQ Ic nv HW rk vL 
bz WB Fi gN lR bW RJ pX zv tO yn Mi th QH kt QV Dh cx Xo wn fD CI Mn Jd Sl oa 
Ua Bt cd kc bL xB fH Ps dN WE dO Bj Xo wn BT bz dx sL ZU Zd yH gZ gt Aj CR vL 
kg zc xt pj sE HW rk br dr Zd Nv wX cu xM Tk ZH OV ks yw Os wQ Er QC il rz FQ 
SL lZ yv AW ps fk gk mt KL gN GL pa sY sg za ac UN rB NX Ar wQ Bq Qx zp jg Wr 
IF EU ab bk Lp by ta Ug wl ig Zj zS RW pH dr iM lY bN Yt Ft dn QM ht rq qI jp 
kT GU eg uM fr kn WI YH ER fa kI jy aB sp nM jR xw Md Nz vb AP Ma pQ ZI gC Go 
sI Ux de rX GP DL mX cU yv Hy Fm ZO rz Mt kf Bv HB mo Fi Qy Qx zp tZ mN PJ Ux 
YF oa lO eD dn gU BJ cG ER mX JY zG CQ IJ YJ Eb QC lN br qB BT bz SJ Bl nD Rt 
CD Py CQ jE aO EU hu Rt uE FV wl RQ dr Mi vy UK fZ Bq yF VJ ks Px wb bP Nx wX 
cu xM Nz vb AP Ma pQ ZI af sO Op qf Rp UK fZ SL Bw kv GA Ax aW Nb aW cj KL Vf 
eJ Tl pW eI gK oE vy jb uN sy ku Yr dn CO bz mN dk vk WO Dz md UA OX cT al ed 
qf SR xm gU cn DY qP SA iM Ax Yl gZ tQ vI Ku qt Bm HW kI pz li YF Iy UM sl oE 
mv xB as zS up Dz PQ UM Nv Ow ks yl ps rX XU Nm cJ Ic Qp tM hQ jy wZ Vb YE Uy 
Mh tb Zf ph Bw Gu lO DY Aw jR dm Uy Kz vy nc Qv al dn za BM Tg Gz NU ch kI RT 
tE Nb di zc JB yZ wZ Ic Qp AV na rX eG GU KZ sy Tk VF gk 

Conditions

My own attempts

Yep, I'm enrolling in the challenge myself. I might win the magnets, who knows ;-)

Honorary Mention: Parallel Approach

After my C++ lectures in 2012, two students of the University of Groningen took up the challenge to implement an OTG cracker on a massive multi-node supercomputer. Joren Heit and Erik Mulder published their findings in January 2013, and I'm very proud to add this information to my site. Without further ado, here is the report in PDF. Licensing information is contained within; basically, you're free to reproduce it - with attribution - just as I am now.