I can think of a couple of ways of doing that
Scanning memory from EIP
You could easily get the EIP of your own code without calling any APIs. There are a few ways to achieve that using inline assembly, but the most common one is to include the following two instructions:
call $+5
pop eax
This works because call will push the next address (where pop eax is onto the stack) and then execute the instruction right after it (again, our pop eax). When pop eax is executed, it'll pop the address just pushed by call $+5 into a register.
After you got your EIP value you can easily scan backwards as you thought of doing, but this time starting at a position a lot closer to your image base.
Keeping in mind image bases are aligned to page boundaries, you can scan in PAGE_SIZE (4096 bytes) intervals.
Reading loaded modules from PEB
The Process Environment Block (also here) structure is accessible using a designated segment register (fs on 32 bit systems and gs on 64 bit systems) which stores the address of the Thread Information Block from which the PEB is reachable. Although most of the PEB is undocumented, in it is a lot of data relating to the operational aspects of the currently running process.
One such piece of information is the ImageBaseAddress, an undocumented (but consistent) field that holds the process's image base. If you're interested in the .exe's image base (opposed to a loaded DLLs image base), this will do.
If you want something more reliable you could use the Ldr member, which points to a PEB_LDR_DATA structure which points to a linked list of LDR_DATA_TABLE_ENTRYs, which lists all loaded modules, their addresses and a lot of other information about each loaded module. Your executable's image base is the DllBase field.
PEB.ImageBaseAddresswill be easier than walking the Ldr structures. – josh poley Oct 18 '18 at 19:10eipin0x1000intervals. If you meant something like:while(*(WORD*)eip != 'ZM') (DWORD)eip -= PAGE_SIZE;, then what if the image base actually was0x400000and theeipwas, say,0x400ABC? Am I missing something? – Jason Oct 18 '18 at 19:45eip & ~(4096-1)– NirIzr Oct 18 '18 at 19:49