EB:imm8 - near jmp.
Where commands start and end.Why 2+2=3.
---------------------------------------
Though this part is based on very simple facts,
not every coder can see subsequences that follow the facts.
So you'd better don't treat it too light.
Open our testing NopProgramm.Don't run it, and don't type anything.
Look at your left - column with addresses of code command.
What is address of start command(this "start command address" is
marked black in OllyDbg)
In my prog it is:
00401000 > 90 NOP
Look at your right at registers window.
Look at register EIP value.
What value it has?
In my prog is is:
EIP 00401000

EIP has address of some byte in memory.
This address it will accept as start of some command.
While it doesn't have the bytes in memory loaded and decoded
as command it doesn't know where the end of it yet.

Let's run first command.
Press F8.
Look what address (on your left) is marked black now.
Look at EIP what value it has.

00401001 90 NOP ;address of next nop
00401001 ;the same value in EIP.

EIP has address of next byte in memory and will treat as
next command. This next byte is address of byte NEXT to
end of previous command.

If you think that I didn't write
"EIP has address of next COMMAND" because of my bad English,
you are wrong.
(You are not wrong about my bad English though :))
Yes, bytes is about to be decoded and executed as next command.
If everything will be OK :)
Actually those bytes might be just some garbege and if
processor doesn't recognize it as command in decoding stage it
rises exeption.
Type OPCODE in place of nops with black mark on address:
FFFF
OllyDbg doesn't recognize it as command,
you can see ??? on MNEMONIC field.
Yet you can see that EIP pointed to this memory where we've inserted FFFFh
bytes to.
So despite of garbage there (right words for that garbage are "illegal opcode")
processor is about to decode and exucute it.
Let's try to execute it.
Press F8.
You can see error message.
Processor has rised exeption. And OllyDbg that intercept it is asking you
what to do with it.
Press OK and change FFFF back to 9090.
Type different mnemonic, with long opcode
for example using lea command.
Execute it paying attention to EIP, and size of command.
You can see that processor recognized size of command and
points now to the nop that is next to your last inserted command.
How he did it?
It took it from opcode decoding. Not as number inside, but
as format from wich it can see all building blocks and
size of them, if size may differ sertain bits show what
size of some block is used.
Example:
near jmp has format
EB:imm8
Two bytes.
EB is CODE field and when EIP pints to
memory where are bytes EB 09
it knows after decoding first byte and recognizing EB code that
length of command is 2 bytes.

Preliminary answers to our question is.
1. Start: Processor treat as start of command fist byte
of memory were it points to.
2. End: Processor knows end of command in decoding stage taking
this info from opcode structure (in many cases from CODE block)
3. If command is not of "control type" then start of the next
command will be memory address of byte next to end of current command.
Pay attention:
And untill it is loaded processor has no idea if those bytes in
EIP are really LEGAL COMMAND.
Now reread (3.)
What is "control type" commands?
It is ret, call, jmp, jcc, int.
What have they got in common?
Don't say, please: "they jump to some address"
Or even worse statement:"they jump to some other place then address of
next command"
To get feelling why it's wrong TYPE OPCODE:
EB 00
Press Enter, and run it (F8).
Where does it jump?
You can see the answer:
Processor just stepped to the next command.
As if it was usual, "not of control type" opcode.
Example of why 1st statement is also wrong:
TYPE OPCODE EB FE
Run it. (Use always F8 not F9!)
EIP doesn't go anywhere.
As if all things stop responding.
At least after usual command processor steps to the next command.
At this case it nor steps neither jump anywere.

Real low level coder calls real things by there real names.
Not by subsequences or whatever.
So real coder doesn't say that cmp command compares anything.
He'd say that cmp command substucts second operand from the first
operand, set flags according to what happens during operation and
what special is about result, but it doesn't write result into
first operand. It is primary meaning or cmp command, it what it does.
The other things is for you can use it for.
If you know how it really works you can use cmp command for anything
it is good for. Not only for comparing.
And you are already know that there no such thing as cmp command.
There are only opcodes that to simple logical, arithmetic and data
transformation\writing\reading operations.

Back to "control commands".
What they really do?
The answer is :All of them changes EIP register.
End you know that value in EIP register is memory address of data that
processor treats as start of command.

What value we can get into EIP then using those "control" commands?
The answer is ANY 32 bit value if you know opcode and algos of those
commands well.
Simple conclusion is that it means that we may force processor treat
any byte in memory as start of next command.

TYPE OPCODE 04 AC
you can see
00401008 04 AC ADD AL,0AC
But you also know that ACh is opcode for lodsb
Address 00401008 is start of opcode 04AC (add al,0AC)
but what code is pointed by 00401009?
If we have pointer (EIP!!!) to 00401009 then we
know that processor whould treat ACh not as operand of
04:imm8 (AL+imm8)
but as different opcode ACh -> lodsb.
Now what if we need to write algo
IF ZF= 0
add al,ACh
ELSE
lodsb
Try to write the algo in mnemonics.



Now look at this asm code:
jne $+1
add al,ACh
That is all we need.
Don't run it untill you know what is in your .
if not zf then address of EIP would be second byte of add al,ACh command
and since we know from opcode that second byte has value ACh and opcode
ACh means lodsb we wrote the whole algo using just 4 bytes!

00401005 75 01 JNZ SHORT
00401007 04 AC ADD AL,0AC
Lets look what each byte means
75:imm opcode format for JNE(75) to address = address of next command + imm8
in other words
after 7501 decoded address of EIP = address of next command
and 01 added to EIP and we get in EIP address of SECOND BYTE of the next
command
Next opcode
04 AC
Format
04:imm8 add to al imm8 (next byte of opcode)
AC = lodsb as you know.
Both opcodes have two blocks format.



If ZF=0 7501 opcode will add to address of next opcode in EIP 1
making it point to second byte of next opcode that has value ACh
and force it treat it as start of new opcode.
Else EIP will point to 04AC and start of next opcode will be byte
04h from it processor will recognize format 04:imm8 (add al,imm8)
and will treat now ACh as operand, not as opcode.

Now let see who is fastest and smartest low level coder here :)

Write me 4 byte opcode algo that do
IF ZF=1
inc eax
ELSE
mov al,40
In hex,please.

And test in your test app.
Posted on 2002-11-16 20:31:00 by The Svin
I hope you meant 'mov al, 40h'

74h, 01h, B0h, 40h




If you meant 40 in decimal:

74h, 02h, B0h, 27h, 40h


but that's 5 bytes. :(
Posted on 2002-11-16 22:21:40 by iblis
Well done!
Yes, I meant 40h.
You are the best!
Posted on 2002-11-16 22:41:31 by The Svin
Another test for fast and smart lowlevel coder:
if PF=1
set all bits in eax to 1
else
set all bit in AX to 1 (don't change upper 16 bits in eax if not PF)

5 byte solution.
Who will be the fastest now?
Posted on 2002-11-16 23:05:52 by The Svin
I'm stumped. :(

This one uses STC in order for SBB to work. I don't know a smaller way to set all bits to 1. It's 6 bytes, not 5. :(

F9, 7A, 01, 66, 1B, C0

(assume 32 bit addressing mode)
Posted on 2002-11-17 00:14:14 by iblis
As long as your using an extra byte: 7A 01 66 83 C8 FF :)

?? ?? 7B 01 98 :confused:
Posted on 2002-11-17 01:49:12 by bitRAKE
Svin, so whats the solution?
Posted on 2002-11-20 10:55:45 by nyook

Svin, so whats the solution?

:)

If you tried to find solution really hard (and
this is all the tuts about - to make your brain work)
You can give me solution to the next exersize in a few
seconds:
if PF = 1 set low 16 bits in eax to ZERO (don't touch upper bits)
else set all 32 bits in eax to ZERO.
5 bytes.
Posted on 2002-11-20 11:54:27 by The Svin
jpe $+3
xor ax,ax

7A 01 66 31 C0
much easier problem.
Posted on 2002-11-20 12:35:08 by bitRAKE
yes, setting bits to 0 is much easier and I found this solution the day you posted this, but then I recognized that it has to be filled with 1 :(
Posted on 2002-11-20 13:20:36 by nyook
It would be possible to brute force the solution or guarantee there is no solution to setting the bits to 1 in five bytes.
Posted on 2002-11-20 13:56:35 by bitRAKE

It would be possible to brute force the solution or guarantee there is no solution to setting the bits to 1 in five bytes.


Exactly!!!
It is approach that used it mose brain force field - MATH.

Example:
Question
Is it possible to have a number
(n+1)^2
that have sum of digits = (n-1)/2

Give the number or prove that it is impossibe.
But prove!

Working on such problem you benefit anyway.
As we did seeing 3 intresting examples of code.
Posted on 2002-11-20 14:32:37 by The Svin
In my previous post I was almost going to say "It's impossible to do in 5 bytes." but I didn't want to say it and look like an idiot if somebody proved me wrong. ;)
Posted on 2002-11-20 17:21:50 by iblis
Svin, I want to verify I understand the problem
Here are some test values:
 n  (n+1)^2 SumDigits (n-1)/2

--- ------- --------- -------
0 1 1 -0.5
1 4 4 0
2 9 9 0.5
3 16 7 1
4 25 7 1.5
5 36 9 2
6 49 13 2.5
7 64 10 3
8 81 9 3.5
9 100 1 4
iblis, still can't say it is impossible. I felt the same way after twenty minutes, but I have found solutions after much longer times. I prefer to invest time in creating a method to brute force such problems. ;)
Posted on 2002-11-20 17:23:36 by bitRAKE
Hi bitRAKE :)
Brute force testing is ok.. but how would one verify the correctness of each code sequence?

BTW: from another quick look at the problem, a bell in my brain ringed on the LAHF instruction.. but I'm not sure it will help us.
Posted on 2002-11-20 18:08:07 by Maverick
The people on this message board are very good at figuring things out. And I think the fact that nobody here can figure it out increases the likelihood that it is indeed impossible to do in 5 bytes. I don't even think Svin knows how to do it in 5 bytes. (no offense) I think that '5' was a typo. ;) Either that or Svin intended it to be a trick question.


In order to prove that it is impossible we need to consider all the factors. Firstly, we need to observe the need to check the parity flag and figure out all the ways in which that can be done. So far I only know of a few operations that can be used to check the status of the parity flag.

SETPO/SETPE - takes 3 bytes
JPO/JPE - short jump takes 2 bytes
LAHF - takes 1 byte

Of course you don't even need to check the parity flag if you could figure out how to manually count the bits of the result of the last operation, but this isn't an option, nor is it likely possible to do in under 5 bytes.


So here are the problems:

1) Best case scenario - using LAHF gives us 4 bytes to work with. What are all the ways using LAHF to set eax/ax to -1? And are any of those under 4 bytes? I doubt it.

2) 2nd best scenario - using JPO/JPE gives us 3 bytes to work with. What are all the ways to set eax/ax to -1 in 3 bytes and have it depend on where JPO/JPE jumps to? It would either a) jump over a whole instruction or b) jump part-way into an instruction.

3) Worst scenario - using SETPO/SETPE gives us 2 bytes to work with. What are all the ways to set eax/ax to -1 in 2 bytes depending on the results of SETPO/SETPE?


(I haven't proved anything, but I've given a place to start. Let's discuss it further.)


Another option is "brute force" which I think means to test all 1,099,511,627,776 possible byte combinations (minus all the invalid opcodes of course) and see which one gives the desired results. Anybody feel up to that task? :grin:
Posted on 2002-11-20 18:18:38 by iblis


Hi bitRAKE :)
Brute force testing is ok.. but how would one verify the correctness of each code sequence?
Set parity, JMP, test result; cleat parity, JMP test result. ;) If it fails then we increment the address space. The harder problem is traping all the bad code that could be in the test space - in comes custom OS. ;) Other solutions would work, but they would be a lot slower, imho. It is possible to get false positives, but they would be few and easy to identify, imho.
Posted on 2002-11-20 18:20:03 by bitRAKE

The people on this message board are very good at figuring things out. And I think the fact that nobody here can figure it out increases the likelihood that it is indeed impossible to do in 5 bytes. I don't even think Svin knows how to do it in 5 bytes. (no offense) I think that '5' was a typo. ;) Either that or Svin intended it to be a trick question.
I totally agree!
Another option is "brute force" which I think means to test all 1,099,511,627,776 possible byte combinations (minus all the invalid opcodes of course) and see which one gives the desired results. Anybody feel up to that task? :grin:
?? ?? 7B 01 98, just need to find a way to set ax=-1 in two bytes. :) Your logic is good, but you fail to test all non-linear methods! :) What about two overlaping pieces of code? Bottom line is that has to be brute forced to be sure and 5 bytes is a piece of cake once you design the test environment. ;) Don't get me wrong - I don't think it is possible - just stating problems with your methodology.
Posted on 2002-11-20 18:27:47 by bitRAKE
I know, I was just giving a jumping-off point we could use for discussion. ;) I don't have any 'method' of disproving it except for talking about it. ;)

Oh and I did touch briefly on overlapping codes when I said: "b) jump part-way into an instruction." which implies overlapping. But I said it only for JPO/JPE because overlapping codes are useless without conditional jump.
Posted on 2002-11-20 18:32:46 by iblis
iblis, I like very mush to follow the way you think.
But please, when you discuss opcode, type opcode along with menmonics.

bitRake, about (n+1)^2 and (n-1)/2,
yes, you understand correctly.

It's exercize from another part of book, discussing
position numeric systems.

To all,
I ask you again.
Please, recommend readers some manual with good opcode reference.
I explained why I had not been able to it: my main manual
is paper book and in Russian.
Posted on 2002-11-20 22:26:56 by The Svin