An aerial search found an oil spill near the submarine's dive location, and two navy vessels with sonar capability had been deployed to assist in the search, officials said.
The oil slick could indicate damage to the vessel or could be a signal from the crew, the navy said.
Chief of staff Yudo said authorities had found an item with "high magnetic force" floating at a depth of 50 to 100 metres.
MODERNISATION 'IMPERATIVE'
Indonesia has been seeking to modernise its defence capabilities but some of its equipment is old and there have been fatal accidents in recent years.
Subianto said it was "imperative" that Indonesia modernises its defence equipment faster, but did not suggest there had been problems with the missing vessel.
Navy spokesman Julius Widjojono told KompasTV that the diesel-powered submarine that runs on electric batteries while submerged could sustain a depth of 250-500 metres (820-1,640 ft).
Read Also: Search for missing Indonesian submarine enters second day as neighbours offer help
"Anything more than that can be pretty fatal, dangerous," the spokesman told KompasTV.
The waters in the area are shallower than in other parts of the archipelago but can still reach depths of more than 1,500 metres.
The navy on Wednesday said a blackout may have occurred during static diving, causing a loss of control and preventing emergency procedures from being carried out if the vessel falls to a depth of 600-700 metres.
Military chief Hadi Tjahjanto on Wednesday told Reuters contact with the submarine was lost at 4:30 a.m. and a search was under way 60 miles (96 km) off Bali.
Indonesia in the past operated a fleet of 12 submarines bought from the Soviet Union to patrol the waters of the sprawling archipelago.
It now operates five - the two German-built Type 209 submarines and three newer South Korean vessels.